溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章主要介紹“Java和C++如何在排序數組中查找數字出現的次數”，在日常操作中，相信很多人在Java和C++如何在排序數組中查找數字出現的次數問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”Java和C++如何在排序數組中查找數字出現的次數”的疑惑有所幫助！接下來，請跟著小編一起來學習吧！
統(tǒng)計一個數字在排序數組中出現的次數。
示例 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 是一個非遞減數組
-10^9 <= target <= 10^9
統(tǒng)計一個數字在排序數組中出現的次數。
樣例：
如樣例所示，nums = [5,7,7,8,8,10]，target = 8，8在數組中出現的次數為2，于是最后返回2。
數組有序，因此可以使用二分來做。兩次二分，第一次二分查找第一個>= target的位置begin；第二次二分查找最后一個<= target的位置end，查找成功則返回end - begin + 1，即為數字在排序數組中出現的次數，否則返回0，表示該數沒有在數組中出現。
二分模板：
模板1
當我們將區(qū)間[l, r]劃分成[l, mid]和[mid + 1, r]時，其更新操作是r = mid或者l = mid + 1，計算mid時不需要加1，即mid = (l + r)/2。
C++/java代碼模板：
int bsearch_1(int l, int r)
{
while (l < r)
{
int mid = (l + r)/2;
if (check(mid)) r = mid;
else l = mid + 1;
}
return l;
}模板2
當我們將區(qū)間[l, r]劃分成[l, mid - 1]和[mid, r]時，其更新操作是r = mid - 1或者l = mid，此時為了防止死循環(huán)，計算mid時需要加1，即mid = ( l + r + 1 ) /2。
C++/java 代碼模板：
int bsearch_2(int l, int r)
{
while (l < r)
{
int mid = ( l + r + 1 ) /2;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}為什么兩個二分模板的mid取值不同？
對于第二個模板，當我們更新區(qū)間時，如果左邊界l更新為l = mid，此時mid的取值就應為mid = (l + r + 1)/ 2。因為當右邊界r = l + 1時，此時mid = (l + l + 1)/2，相當于下取整，mid為l，左邊界再次更新為l = mid = l，相當于沒有變化。while循環(huán)就會陷入死循環(huán)。因此，我們總結出來一個小技巧，當左邊界要更新為l = mid時，我們就令 mid =(l + r + 1)/2，相當于上取整，此時就不會因為r取特殊值r = l + 1而陷入死循環(huán)了。
而對于第一個模板，如果左邊界l更新為l = mid + 1，是不會出現這樣的困擾的。因此，大家可以熟記這兩個二分模板，基本上可以解決99%以上的二分問題，再也不會被二分的邊界取值所困擾了。
什么時候用模板1？什么時候用模板2？
假設初始時我們的二分區(qū)間為[l,r]，每次二分縮小區(qū)間時，如果左邊界l要更新為 l = mid，此時我們就要使用模板2，讓 mid = (l + r + 1)/ 2，否則while會陷入死循環(huán)。如果左邊界l更新為l = mid + 1,此時我們就使用模板1，讓mid = (l + r)/2。因此，模板1和模板2本質上是根據代碼來區(qū)分的，而不是應用場景。如果寫完之后發(fā)現是l = mid，那么在計算mid時需要加上1，否則如果寫完之后發(fā)現是l = mid + 1，那么在計算mid時不能加1。
為什么模板要取while( l < r)，而不是while( l <= r)？
本質上取l < r 和 l <= r是沒有任何區(qū)別的，只是習慣問題，如果取l <= r，只需要修改對應的更新區(qū)間即可。
while循環(huán)結束條件是l >= r，但為什么二分結束時我們優(yōu)先取r而不是l?
二分的while循環(huán)的結束條件是l >= r，所以在循環(huán)結束時l有可能會大于r，此時就可能導致越界，二分問題我們優(yōu)先取r。
二分查找的實現細節(jié)：
1、二分查找時，首先要確定我們要查找的邊界值，保證每次二分縮小區(qū)間時，邊界值始終包含在內。
2、注意看下面的每張圖，最后的答案就是紅色箭頭指出的位置，也是我們二分的邊界值。如果不清楚每次二分時，區(qū)間是如何更新的，可以畫出和下面類似的圖，每次更新區(qū)間時，要保證邊值始終包含在內，這樣關于左右邊界的更新就會一目了然。
第一次查找target起始位置:
1、二分的范圍，l = 0， r = nums.size() - 1，我們去二分查找>= target的最左邊界begin。
2、當nums[mid] >= target時，往左半區(qū)域找，r = mid。
3、當nums[mid] < target時， 往右半區(qū)域找，l = mid + 1。
4、如果nums[r] != target，說明數組中不存在目標值 target，返回 0。否則我們就找到了第一個>=target的位置begin。
第二次查找target結束位置：
1、二分的范圍，l = 0， r = nums.size() - 1，我們去二分查找<= target的最右邊界end。
2、當nums[mid] <= target時，往右半區(qū)域找，l = mid。
3、當nums[mid] > target時， 往左半區(qū)域找，r = mid - 1。
4、找到了最后一個<= target的位置begin，返回end - begin + 1即可。
時間復雜度分析： 兩次二分查找的時間復雜度為 O ( l o g n ) O(logn)O(logn)。
空間復雜度分析： 沒有使用額外的數組，因此空間復雜度為O ( 1 ) O(1)O(1)。
class Solution {
public:
int search(vector<int>& nums, int target) {
if(!nums.size()) return 0;
int l = 0, r = nums.size() - 1;
while(l < r) //查找target的開始位置
{
int mid = (l + r) / 2;
if(nums[mid] >= target) r = mid;
else l = mid + 1;
}
if(nums[r] != target) return 0 ; //查找失敗
int begin = r; //記錄開始位置
l = 0, r = nums.size() - 1;
while(l < r) //查找tatget的結束位置
{
int mid = (l + r + 1) / 2;
if(nums[mid] <= target) l = mid;
else r = mid - 1;
}
int end = r; //記錄結束位置
return end - begin + 1;
}
};class Solution {
public int search(int[] nums, int target) {
if(nums.length == 0) return 0;
int l = 0, r = nums.length - 1;
while(l < r) //查找target的開始位置
{
int mid = (l + r) / 2;
if(nums[mid] >= target) r = mid;
else l = mid + 1;
}
if(nums[r] != target) return 0 ; //查找失敗
int begin = r; //記錄開始位置
l = 0; r = nums.length - 1;
while(l < r) //查找tatget的結束位置
{
int mid = (l + r + 1) / 2;
if(nums[mid] <= target) l = mid;
else r = mid - 1;
}
int end = r; //記錄結束位置
return end - begin + 1;
}
}到此，關于“Java和C++如何在排序數組中查找數字出現的次數”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續(xù)學習更多相關知識，請繼續(xù)關注億速云網站，小編會繼續(xù)努力為大家?guī)砀鄬嵱玫奈恼拢?/p>
免責聲明：本站發(fā)布的內容（圖片、視頻和文字）以原創(chuàng)、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
