剑指Offer_37

发表于 | 分类于

题目

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

解题思路

二分搜索法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public class Solution {
    public int GetNumberOfK(int [] array , int k) {
        if(array == null || array.length == 0){
            return 0;
        }
       
        int lo = 0;
        int hi = array.length-1;
        int mid = 0;
        int cnt = 0;
        
        while(lo <= hi){
            mid = (hi + lo) >> 1;
            if(array[mid] < k){
                lo = mid + 1;
            }
            else if(array[mid] > k){
                hi = mid - 1;
            }
            else{
                cnt = 1;
                break;
            }
        }
        
        if(cnt == 0){
            return 0;
        }
        
        int i = mid - 1;
        int j = mid + 1;
        while(i >= 0 && array[i--] == k) { ++cnt; }
        while(j < array.length && array[j++] == k) { ++cnt; }
        
        return cnt;
    }
}