二分查找--数字在排序数组中出现的次数
程序员文章站
2022-03-14 23:50:56
...
统计一个数字在排序数组中出现的次数。
看到有序数组,第一反应就应该是二分查找,复杂度为O(logn),比从头到尾扫描复杂度O(n)效率高。分别用二分查找法第一次和最后一次出现的数字的下标,相减即可、
class Solution {
public:
int GetNumberOfK(vector<int> data ,int k) {
int number=0;
int a=Getfirstnumber( data ,0,data.size()-1,k);
int b=Getlastnumber(data ,0,data.size()-1,k);
if(a>-1&&b>-1)
number=b-a+1;
return number;
}
int Getfirstnumber(vector<int> data ,int start,int end,int k) {
if(start>end)
return -1;
int middle =(start+end)/2;
if( data[middle]==k)
{
if(middle==start||( middle-1>=start&&data[middle-1]!=k))
return middle;
else
end= middle-1;
}
else if(data[middle]>k)
{end=middle-1;
}
else
start=middle+1;
return Getfirstnumber(data ,start,end,k);
}
int Getlastnumber(vector<int> data ,int start,int end,int k) {
if(start>end)
return -1;
int middle =(start+end)/2;
if( data[middle]==k)
{
if((middle+1<=end&&data[middle+1]!=k)||middle==end)
return middle;
else
start=middle+1;
}
else if(data[middle]>k)
{end=middle-1;
}
else
{ start=middle+1;
}
return Getlastnumber(data ,start, end,k);
}
};
注意:边界条件。
若是使用STL :
int GetNumberOfK(vector<int> data ,int k) {
return count(data.begin(),data.end(),k);
}注意count()是顺序查找,复杂度o(n)
auto p1 = lower_bound(data.begin(), data.end(), k);
auto p2 = upper_bound(data.begin(), data.end(), k);
return p2 - p1;
upper_bound(i) 返回的是键值为i的元素可以插入的最后一个位置(上界)
lowe_bound(i) 返回的是键值为i的元素可以插入的位置的第一个位置(下界)。
为二分查找。当容器中没有要查找的元素时,返回值是一样的。
推荐阅读
-
PHP查找数组中只出现一次的数字实现方法【查找特定元素】
-
PHP实现统计一个数字在排序数组中出现次数的方法
-
LeetCode 面试题56 - I. 数组中数字出现的次数
-
在一个非降序排列的数组中,找出数字target出现的次数问题解答
-
剑指offer 56 数组中数字出现的次数 lintcode 82. 落单的数、83. 落单的数 II、84. 落单的数 III
-
牛客之数字在排序数组中出现的次数
-
在排序数组中查找元素的第一个和最后一个位置、变形二分法
-
#leetcode刷题之路34-在排序数组中查找元素的第一个和最后一个位置
-
34. 在排序数组中查找元素的第一个和最后一个位置
-
Leetcode No.34 在排序数组中查找元素的第一个和最后一个位置