1、題目

統(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

2、思路

統(tǒng)計(jì)一個(gè)數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)。

樣例：

如樣例所示，nums = [5,7,7,8,8,10]，target = 8，8在數(shù)組中出現(xiàn)的次數(shù)為2，于是最后返回2。

數(shù)組有序，因此可以使用二分來(lái)做。兩次二分，第一次二分查找第一個(gè)>= target的位置begin；第二次二分查找最后一個(gè)<= target的位置end，查找成功則返回end - begin + 1，即為數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)，否則返回0，表示該數(shù)沒有在數(shù)組中出現(xiàn)。

二分模板：

模板1

當(dāng)我們將區(qū)間[l, r]劃分成[l, mid]和[mid + 1, r]時(shí)，其更新操作是r = mid或者l = mid + 1，計(jì)算mid時(shí)不需要加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

當(dāng)我們將區(qū)間[l, r]劃分成[l, mid - 1]和[mid, r]時(shí)，其更新操作是r = mid - 1或者l = mid，此時(shí)為了防止死循環(huán)，計(jì)算mid時(shí)需要加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;
}

為什么兩個(gè)二分模板的mid取值不同？

對(duì)于第二個(gè)模板，當(dāng)我們更新區(qū)間時(shí)，如果左邊界l更新為l = mid，此時(shí)mid的取值就應(yīng)為mid = (l + r + 1)/ 2。因?yàn)楫?dāng)右邊界r = l + 1時(shí)，此時(shí)mid = (l + l + 1)/2，相當(dāng)于下取整，mid為l，左邊界再次更新為l = mid = l，相當(dāng)于沒有變化。while循環(huán)就會(huì)陷入死循環(huán)。因此，我們總結(jié)出來(lái)一個(gè)小技巧，當(dāng)左邊界要更新為l = mid時(shí)，我們就令 mid =(l + r + 1)/2，相當(dāng)于上取整，此時(shí)就不會(huì)因?yàn)閞取特殊值r = l + 1而陷入死循環(huán)了。

而對(duì)于第一個(gè)模板，如果左邊界l更新為l = mid + 1，是不會(huì)出現(xiàn)這樣的困擾的。因此，大家可以熟記這兩個(gè)二分模板，基本上可以解決99%以上的二分問題，再也不會(huì)被二分的邊界取值所困擾了。

什么時(shí)候用模板1？什么時(shí)候用模板2？

假設(shè)初始時(shí)我們的二分區(qū)間為[l,r]，每次二分縮小區(qū)間時(shí)，如果左邊界l要更新為 l = mid，此時(shí)我們就要使用模板2，讓 mid = (l + r + 1)/ 2，否則while會(huì)陷入死循環(huán)。如果左邊界l更新為l = mid + 1,此時(shí)我們就使用模板1，讓mid = (l + r)/2。因此，模板1和模板2本質(zhì)上是根據(jù)代碼來(lái)區(qū)分的，而不是應(yīng)用場(chǎng)景。如果寫完之后發(fā)現(xiàn)是l = mid，那么在計(jì)算mid時(shí)需要加上1，否則如果寫完之后發(fā)現(xiàn)是l = mid + 1，那么在計(jì)算mid時(shí)不能加1。

為什么模板要取while( l < r)，而不是while( l <= r)？

本質(zhì)上取l < r 和 l <= r是沒有任何區(qū)別的，只是習(xí)慣問題，如果取l <= r，只需要修改對(duì)應(yīng)的更新區(qū)間即可。

while循環(huán)結(jié)束條件是l >= r，但為什么二分結(jié)束時(shí)我們優(yōu)先取r而不是l?

二分的while循環(huán)的結(jié)束條件是l >= r，所以在循環(huán)結(jié)束時(shí)l有可能會(huì)大于r，此時(shí)就可能導(dǎo)致越界，二分問題我們優(yōu)先取r。

二分查找的實(shí)現(xiàn)細(xì)節(jié)：

1、二分查找時(shí)，首先要確定我們要查找的邊界值，保證每次二分縮小區(qū)間時(shí)，邊界值始終包含在內(nèi)。

2、注意看下面的每張圖，最后的答案就是紅色箭頭指出的位置，也是我們二分的邊界值。如果不清楚每次二分時(shí)，區(qū)間是如何更新的，可以畫出和下面類似的圖，每次更新區(qū)間時(shí)，要保證邊值始終包含在內(nèi)，這樣關(guān)于左右邊界的更新就會(huì)一目了然。

第一次查找target起始位置:

1、二分的范圍，l = 0， r = nums.size() - 1，我們?nèi)ザ植檎?gt;= target的最左邊界begin。

2、當(dāng)nums[mid] >= target時(shí)，往左半?yún)^(qū)域找，r = mid。

3、當(dāng)nums[mid] < target時(shí)， 往右半?yún)^(qū)域找，l = mid + 1。

4、如果nums[r] != target，說明數(shù)組中不存在目標(biāo)值 target，返回 0。否則我們就找到了第一個(gè)>=target的位置begin。

第二次查找target結(jié)束位置：

1、二分的范圍，l = 0， r = nums.size() - 1，我們?nèi)ザ植檎?lt;= target的最右邊界end。

2、當(dāng)nums[mid] <= target時(shí)，往右半?yún)^(qū)域找，l = mid。

3、當(dāng)nums[mid] > target時(shí)， 往左半?yún)^(qū)域找，r = mid - 1。

4、找到了最后一個(gè)<= target的位置begin，返回end - begin + 1即可。

時(shí)間復(fù)雜度分析： 兩次二分查找的時(shí)間復(fù)雜度為 O ( l o g n ) O(logn)O(logn)。

空間復(fù)雜度分析： 沒有使用額外的數(shù)組，因此空間復(fù)雜度為O ( 1 ) O(1)O(1)。

3、c++代碼

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的結(jié)束位置
        {
            int mid = (l + r + 1) / 2;
            if(nums[mid] <= target) l = mid;
            else r = mid - 1;
        }
        int end = r;       //記錄結(jié)束位置      
        return end - begin + 1;
    } 
};

4、java代碼

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的結(jié)束位置
        {
            int mid = (l + r + 1) / 2;
            if(nums[mid] <= target) l = mid;
            else r = mid - 1;
        }
        int end = r;       //記錄結(jié)束位置      
        return end - begin + 1;  
    }
}

原題鏈接

到此這篇關(guān)于Java C++解決在排序數(shù)組中查找數(shù)字出現(xiàn)次數(shù)問題的文章就介紹到這了,更多相關(guān)Java C++ 在數(shù)組中查找數(shù)字出現(xiàn)次數(shù)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論