剑指offer - 数字在数组中出现的次数(Java实现)

题目链接：https://www.nowcoder.com/practice/70610bf967994b22bb1c26f9ae901fa2?tpId=13&&tqId=11190&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

  思路一：直接遍历数组记录 k 出现的次数。

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

  思路二：由于给出的数组本身是一个升序的数组，所以我们使用二分的方法找到 k 第一次出现的位置，以及 k 最后一次出现的位置，如果找不到则说明数组中不存在该数字。

public class Solution {
    public int GetNumberOfK(int [] array , int k) {
        if(array == null || array.length == 0) return 0;
        int l = lower_bound(array, k);
        int r = upper_bound(array, k);
        return (l == -1 || r == -1) ? 0 : r - l + 1;
    }
    public int lower_bound(int[] array, int k) {
        int l = 0, r = array.length - 1, ans = -1;
        while(l <= r) {
            int mid = (l + r) >> 1;
            if(array[mid] > k) {
                r = mid - 1;
            } else if(array[mid] == k) {//寻找左边第一个
                r = mid - 1;
                ans = mid;
            } else {
                l = mid + 1;
            }
        }
        return ans;
    }
    public int upper_bound(int[] array, int k) {
        int l = 0, r = array.length - 1, ans = -1;
        while(l <= r) {
            int mid = (l + r) >> 1;
            if(array[mid] > k) {
                r = mid - 1;
            } else if(array[mid] == k) {//寻找右边第一个
                l = mid + 1;
                ans = mid;
            } else {
                l = mid + 1;
            }
        }
        return ans;
    }
}