今日份題目：
統(tǒng)計(jì)一個(gè)數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)。
示例1
輸入: nums = [5,7,7,8,8,10], target = 8
輸出: 2示例2
輸入: nums = [5,7,7,8,8,10], target = 6
輸出: 0提示
-
0 <= nums.length <= 10^5 -
-10^9 <= nums[i] <= 10^9 -
nums是一個(gè)非遞減數(shù)組 -
-10^9 <= target <= 10^9
題目思路
使用兩次二分查找找到target在數(shù)組中的左右邊界，然后長度就是右邊界減去左邊界再加一，最后返回長度即可。
代碼
class Solution
{
public:
int binarySearch(vector<int>& nums, int target, bool lower)
{//二分查找，lower為true表示查找第一個(gè)大于等于target的下標(biāo)（左端點(diǎn)），為false表示查找第一個(gè)大于target的下標(biāo)（右端點(diǎn)）
int left=0,right=nums.size()-1,ans=nums.size();
while(left<=right)
{
int mid=(left+right)/2;
if(nums[mid]>target||(lower&&nums[mid]>=target))
{//需要移到左半部分繼續(xù)二分查找
right=mid-1;
ans=mid;
}
else //需要移到右半部分繼續(xù)二分查找
{
left=mid+1;
}
}
return ans;
}
int search(vector<int>& nums, int target)
{
int l=binarySearch(nums,target,true);//二分查找左端點(diǎn)
int r=binarySearch(nums,target,false)-1;//二分查找右端點(diǎn)
if(l<=r&&r<nums.size()&&nums[l]==target&&nums[r]==target)
{//如果存在這樣的全是target這個(gè)數(shù)的區(qū)間，并且未超出nums范圍，并且確定區(qū)間內(nèi)的數(shù)都是target
return r-l+1;
}
return 0;//不符合返回0
}
};
提交結(jié)果
文章來源：http://www.zghlxwxcb.cn/news/detail-630577.html
? 歡迎大家在評論區(qū)討論，如有不懂的代碼部分，歡迎在評論區(qū)留言！文章來源地址http://www.zghlxwxcb.cn/news/detail-630577.html
到了這里，關(guān)于每天一道leetcode：劍指 Offer 53 - I. 在排序數(shù)組中查找數(shù)字 I（適合初學(xué)者&二分查找）的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
