剑指offer——数字在排序数组中出现的次数---AI那点小事

概要

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

思路

由于是有序数组，那么查找采取二分法。找到k在数组中的位置，在向前和向后遍历是否有重复的。

C++ AC代码class Solution { public: int GetNumberOfK(vector<int> data ,int k) { int len = data.size(); /*if(len == 0 || k > data[len-1] || k < data[0]){ return 0; }*/ int left = 0; int right = len-1; int mid = this->Find(data,k,left,right); if(mid == -1){ return 0; } int cnt = 1; int mid_l = mid-1; int mid_r = mid+1; while(left <= mid_l){ if(data[mid_l] == k){ cnt++; mid_l--; }else{ break; } } while(mid_r <= right){ if(data[mid_r] == k){ cnt++; mid_r++; }else{ break; } } return cnt; } int Find(vector<int> data,int k, int left,int right){ while(left <= right){ int mid = (left+right)/2; if(data[mid] < k){ left = mid+1; }else if(data[mid] > k){ right = mid-1; }else{ return mid; } } return -1; } }; ---来自腾讯云社区的---AI那点小事