剑指Offer-数字在排序数组中出现的次数

发表于 | 阅读次数 | 阅读数

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

题目

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

思路

1.遍历
2.根据二分找到第一个出现的位置和最后一个出现的额位置

代码

public class Solution {
    public int GetNumberOfK(int [] array , int k) {
        int firstK = getFirstK(array,k);
        int lastK = getLastK(array,k);
        return lastK-firstK+1;
    }
    private int getLastK(int[] array, int k) {
        int start = 0;
        int end = array.length-1;
        int mid = (start+end)>>1;
        while (start<=end){
            if (array[mid]<=k){
                start = mid+1;
            }else {
                end = mid -1;
            }
            mid = (start+end)>>1;
        }
        return end;
    }

    private int getFirstK(int[] array, int k) {
        int start = 0;
        int end = array.length-1;
        int mid = (start+end)>>1;

        while (start<=end){
            if (array[mid]<k){
                start = mid +1;
            }else {
                end = mid - 1;
            }
            mid = (start+end)>>1;
        }
        return start;
    }
}
0%