剑指Offer

https://www.nowcoder.com/practice/70610bf967994b22bb1c26f9ae901fa2?tpId=13&tqId=11190&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

题目描述

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

 

 

class Solution {
    int findK(vector<int> &data ,int k) {
        int first = 0;
        int last = data.size() - 1;
        
        while (first <= last) {
            int mid = first + (last - first) / 2;
            if (data[mid] == k) return mid;
            else if (data[mid] < k) first = mid + 1;
            else last = mid - 1;
        }
        return -1;
    }
public:
    int GetNumberOfK(vector<int> data ,int k) {
        if (data.size() == 0) return 0;
        int idx = findK(data, k);
        if (idx == -1) return 0;
        int first = idx, last = idx;
        while (first >= 0 && data[first] == data[idx]) first--;
        while (last < data.size() && data[last] == data[idx]) last++;
        return last - first -1;
    }
};