数字在排序数组中出现的次数

写在前面

简直offer：数字在排序数组中出现的次数

题目描述

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

解法

暴力解：遍历数组记录出现个数。时间复杂度为o(n)

进阶解法：

class Solution { public: int GetNumberOfK(vector<int> data ,int k) { if(!data.size()) return 0; int res = 0; //采用二分搜索的方式进行搜索 int l = 0,r = data.size()-1; while(l<=r) {//当只有一个元素的时候，l<r是进不了循环的。这里的判断条件需要带入特殊的值进行判断。 int mid = l + (r-l)/2; if(data[mid]>k) { r = mid-1; } else if(data[mid]<k) { l = mid+1; } else { //如果二分找到k就判断其周围有没有 for(int i=mid;i<=r;++i) { if(data[i]==k) ++res; else break; } for(int i=mid-1;i>=l;--i) { if(data[i]==k) ++res; else break; } break; } } return res; } };

假设数组的长度为n，k元素出现的次数为m次。
算法的时间复杂度为o(logn+m)。如果k出现的次数为n算法的复杂度将退化为o(n)。

有没有更好的解法？

分析： 上面的算法的复杂度来源于当使用二分找到第一个k的时候，还需要在k的两边遍历去寻找重复的k。如何省去这个遍历的过程是改进的关键。
思路：合理利用二分搜索。使用找上界和找下界的方式一次性找到k的上下界这时只需要相减就能够得到k的个数。找上下界的时间复杂度都是o(logn)。所以整个算法的复杂度为o(logn)。

class Solution { public: int GetNumberOfK(vector<int> data ,int k) { if(!data.size()) return 0; int l = getleft(data,k); int r = getright(data,k); if(l==-1&&r==-1) return 0; return r - l + 1; } //找到第一个k的位置 int getleft(vector<int>& data,int k) { int l = 0, r = data.size()-1; while(l<=r) { int mid = l + (r-l)/2; if(data[mid]>k) { r = mid-1; } else if(data[mid]<k) l = mid+1; else { if(mid==0||mid-1>=0&&data[mid-1]!=k) return mid; else r = mid-1; } } return -1; } //找到最后一个k的位置 int getright(vector<int>& data,int k) { int l = 0, r = data.size()-1; while(l<=r) { int mid = l + (r-l)/2; if(data[mid]<k) { l = mid+1; } else if(data[mid]>k) { r = mid-1; } else { if(mid==data.size()-1||mid+1<data.size()&&data[mid+1]!=k) return mid; else l = mid +1; } } return -1; } };