《剑指offer》数字在排序数组中出现的次数

题目链接：?rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

题目描述统计一个数字在排序数组中出现的次数思路因为数组是排好序的，所以我们可以通过二分来找到第一个k和最后一个k，，那么数组中一共有多少个k就很容易求出来了

class Solution{public:int GetNumberOfK(vector<int> data ,int k){int len = data.size();if(len==0)return 0;int l = GetFirstK(data,len,k,0,len-1);int r = GetLastK(data,len,k,0,len-1);if(l>-1 && r>-1)return r-l+1;return 0;}int GetFirstK(vector<int> data,int len,int k,int start,int end){if(start>end)return -1;int midIndex = (start+end)/2;int midData = data[midIndex];if(midData==k){if(midIndex==0 || (midIndex>0 && data[midIndex-1]!=k))return midIndex;elseend = midIndex-1;}else if(midData>k)end = midIndex-1;elsestart = midIndex+1;return GetFirstK(data,len,k,start,end);}int GetLastK(vector<int> data,int len,int k,int start,int end){if(start>end)return -1;int midIndex = (start+end)/2;int midData = data[midIndex];if(midData==k){if(midIndex==len-1 || (midIndex<len-1 && data[midIndex+1]!=k))return midIndex;elsestart = midIndex+1;}else if(midData<k)start = midIndex+1;elseend = midIndex-1;return GetLastK(data,len,k,start,end);}};

没有预兆目的地在哪，前进的脚步不能停下，

相关文章：

你感兴趣的文章：

标签云：