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
       
         &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
        
          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;    }};