找出数字在已排序数组中出现的次数-白红宇

一，问题描述

假设给定一个有序的整型数组arr，以及一个整数 k，问 k在数组中出现了几次？

二，求解思路

①数组是有序的，故可考虑用二分查找

②如果能找到 k 在数组中第一次出现时的索引位置first_index 和最后一次出现时的索引位置last_index

就可以知道 k 出现的次数了: (last_index - first_index) + 1

而对于有序数组而言，可以通过二分查找求出某个数第一次出现的索引位置和 最后一次出现的索引位置。故总的时间复杂度为O(logN)

③特殊情况考虑

k 不在数组中时怎么办？数组arr为null 或者数组 arr.length == 0

核心思路：求解 k 第一次出现时的索引位置

首先找出arr[middle]，如果 k 比中间元素大，则在右边寻找k第一次出现时的索引位置（递归），若 k 比中间元素小，则在左边寻找...（递归）。

若 k == arr[middle]，则需要判断 arr[middle -1] 是否等于 k，若不等于k，则说明 middle 就是 k 第一次出现时的索引；若等于 k，则继续递归在左边寻找，但是此时要注意左边索引不要越界（middle == low 了，就不能再往左边寻找了）。

同理可求解，k 最后一次出现时的索引位置。

三，完整代码实现

public class OccFreq {        /**     * 求解 k 在 arr 中第一次出现的索引位置     * @param arr 有序数组     * @param k     * @return k第一次出现的索引位置,若 k 不在 arr中返回 -1     */    public static int getFirst(int[] arr, int k){        if(arr == null || arr.length == 0)            throw new IllegalArgumentException("arr == null or arr.lenght == 0");                return getFirst(arr, 0, arr.length - 1, k);    }        private static int getFirst(int[] arr, int low, int high, int k){        int middle = (low + high) / 2;        if(middle == low || middle == high)        {            if(arr[middle] == k)                return middle;            else//                throw new IllegalArgumentException(k + " not in arr");                return -1;        }                if(arr[middle] > k)            return getFirst(arr, low, middle - 1, k);        else if(arr[middle] < k)            return getFirst(arr, middle + 1, high, k);        else        {            if(arr[middle - 1] == k)                return getFirst(arr, low, middle - 1, k);            else                return middle;        }    }        /**     * 求解 k 在 arr 中最后一次出现的索引     * @param arr     * @param k     * @return k 在arr中的最后出现的索引, 若 k 不在 arr中返回 -1     */    public static int getLast(int[] arr, int k){        if(arr == null || arr.length == 0)            throw new IllegalArgumentException("arr == null");        return getLast(arr, 0, arr.length - 1, k);    }    private static int getLast(int[] arr, int low, int high, int k){        int middle = (low + high) / 2;        //已经寻找到最左边 或 最右边了.        if(middle == low || middle == high)        {            if(arr[middle] == k)                return middle;            else//                throw new IllegalArgumentException(k + " not in arr");                return -1;//k 不在 arr中        }        if(arr[middle] > k){
   //继续在左边寻找            return getLast(arr, low, middle - 1, k);        }        else if(arr[middle] < k){
   //继续在右边寻找            return getLast(arr, middle + 1, high, k);        }        else//k== arr[middle]        {            if(arr[middle + 1] == k)                return getLast(arr, middle + 1, high, k);//继续在右边寻找            else                return middle;        }    }        /**     * 求解 k 在 arr数组中出现的次数     * @param arr 有序数组     * @param k     * @return k 在 arr 数组中出现的次数     */    public static int freq(int[] arr, int k){        int first_index = getFirst(arr, k);        int last_index = getLast(arr, k);        if(first_index < 0 && last_index < 0)            return 0;        return last_index - first_index + 1;    }        public static void main(String[] args) {        int[] arr = {2,4,5,6,8,8,8,9};            int freqs = freq(arr, 1);        System.out.println(freqs);    }}

本文转自hapjin博客园博客，原文链接：http://www.cnblogs.com/hapjin/p/5674810.html，如需转载请自行联系原作者