小景哥哥

世界很大,而我们还需要再成长!

您现在的位置是:首页>爱编程>详细内容

37.数字在排序数组中出现的次数

发布时间:2018-08-23 00:00:00编辑:Jason浏览(246)评论(0)

    37.数字在排序数组中出现的次数

    题目描述

    统计一个数字在排序数组中出现的次数。
     

    //暴力解决

    public class Solution {
        public int GetNumberOfK1(int [] array , int k) {
           int count = 0;
            for(int i = 0; i < array.length; i++){
                if(array[i] == k)
                    count++;
            }
            return count;
        }

    //基于二分查找思想
        public int GetNumberOfK(int [] array , int k) {
           int count = 0;
            int index = biSearch(array, k, 0, array.length - 1);
            if(index == -1)
                return 0;
            for(int i = index; i < array.length; i++){
                if(array[i] == k)
                    count++;
            }
            return count;
        }
        
        public static int biSearch(int[] array, int k, int low, int high){
            if(low > high)
                return -1;
            int mid = (low + high) / 2;
            int midData = array[mid];
            if(midData == k){
                if(mid > 0 && array[mid - 1] != k || mid == 0)
                    return mid;
                else{
                    while(mid > 0 && array[mid - 1] == k)
                        mid--;
                    return mid;
                }
            }else if(midData > k)
                high = mid - 1;
            else
                low = mid + 1;
            return biSearch(array, k, low, high);
        }
    }

     

关键字词:offer