数字在排序数组中出现的次数 心已赠人 2022-05-17 01:05 123阅读 0赞 #### 写在前面 #### > 简直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; } };
还没有评论,来说两句吧...