IT工程師數位筆記本

統計一個數字在排序數組中出現的次數。

首先吐槽下出題人的用詞，啥叫排序數組？“排序”是個動詞好么，“有序”作為一個形容詞表示狀態，修飾“數組”，才是合適的。

題目考察二分查找，首先找到指定數字最先出現的位置，然后找到最后出現的位置，他們的距離+1就是個數。

class Solution14{
public:
    int GetNumberOfK(vector<int> data, int k){
        if (data.empty()){
            return 0;
        }
        int first = GetFirstIndex(data, k, 0, data.size() - 1);
        int last = GetLastIndex(data, k, 0, data.size() - 1);
        if (first > -1 && last > -1){
            return last - first + 1;
        }
        return 0;
    }
    int GetFirstIndex(vector<int>& data, int k, int start, int end){
        if (start > end) return -1;
        int mid = start + (end - start) / 2;
        if (data[mid] == k){
            if (mid == start || data[mid-1]!=k){
                return mid;
            }
            else{
                end = mid - 1;
            }
        }
        else{
            if (data[mid]>k){
                end = mid - 1;
            }
            else{
                start = mid + 1;
            }
        }
        return GetFirstIndex(data, k, start, end);
    }
    int GetLastIndex(vector<int>& data, int k, int start, int end){
        if (start > end) return -1;
        int mid = start + (end - start) / 2;
        if (data[mid] == k){
            if (mid == end || data[mid + 1] != k){
                return mid;
            }
            else{
                start = mid + 1;
            }
        }
        else{
            if (data[mid]>k){
                end = mid - 1;
            }
            else{
                start = mid + 1;
            }
        }
        return GetLastIndex(data, k, start, end);
    }
};