经典算法：双指针（左右边界问题）

问题描述

给定一个长度为 n 的非降序数组和一个非负数整数 k ，要求统计 k 在数组中出现的次数

数据范围：1000≤n≤1000,0≤k≤100，数组中每个元素的值满足 0≤val≤100
要求：空间复杂度 O(1)，时间复杂度 O(logn)

原题链接：数字在升序数组中出现的次数_牛客题霸_牛客网

思路

充分利用题目条件：有序数组，这样的双指针就可以用了，算法复杂度；

如果暴力算法的话：时间复杂度O(n)

针对本问题：需要分别找到左右边界left right，双指针法；

元素数量就是right - left + 1;

左边界：

中间元素mid的值如果小于k，那么k的左边界一定在mid的右侧；

因此l = mid + 1;

否则r = mid；

右边界：

中间元素mid的值如果大于k，那么k的右边界一定在mid的左侧；

因此r = mid - 1;

否则l = mid；

注意这里mid = (l + r + 1)/2，因为出现两个元素时比如[3,5] 目标元素3，那么如果mid取左侧元素等于目标元素，左侧指针l一直会死循环在这里！因此寻找右边界时需要使其优先取右侧元素！

优化：如果目标元素不在数组范围内则直接返回0；

class Solution {
public:
int GetNumberOfK(vector<int> data ,int k) {
int n = data.size();
if(n <= 0) return 0;
if(n == 1) return data[0]==k?1:0;
if(k > data[n-1] || k < data[0]) return 0;
int l = 0, r = n-1;
int left = 0, right = 0;
int mid;
while(l < r)
{
mid = (r+l)/2;
//if(data[l] == k) break;
if(data[mid] < k)
l = mid+1;
else
r = mid;
}
left = l;
if(data[left] != k) return 0;
l = 0, r = n-1;
while(l < r)
{
mid = (r+l+1)/2;
//if(data[r] == k) break;
if(data[mid] > k)
r = mid-1;
else
l = mid;
}
right = r;
return right - left + 1;
}
};

最后

以上就是懦弱魔镜为你收集整理的经典算法：双指针（左右边界问题）的全部内容，希望文章能够帮你解决经典算法：双指针（左右边界问题）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。