目錄

題目：劍指 Offer 53 - I. 在排序數(shù)組中查找數(shù)字 I - 力扣（Leetcode）

題目的接口：

解題思路：

代碼：

過(guò)啦?。?！

寫(xiě)在最后：

題目：劍指 Offer 53 - I. 在排序數(shù)組中查找數(shù)字 I - 力扣（Leetcode）

題目的接口：

class Solution {
public:
    int search(vector<int>& nums, int target) {

    }
};

解題思路：

那么這道題呢，

如果只是作為一道題，或者說(shuō)筆試題，

我們當(dāng)然是二話不說(shuō)直接暴力拿下，

來(lái)看代碼：

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int cnt = 0;
        for(auto e : nums) if(e == target) cnt++;
        return cnt;        
    }
};

是的，就是這么簡(jiǎn)單，三行代碼暴力拿下，

但是，很顯然，這道題肯定不只是讓你隨便暴力拿下，

如果是在面試的時(shí)候，面試官讓你講講這道題，你確實(shí)可以先給面試官

講講暴力的解法，但要是你只會(huì)暴力，那估計(jì)就要直接回家等通知了，

很顯然，作為一個(gè)有序數(shù)組，這道題可以用二分進(jìn)行優(yōu)化：

我們可以通過(guò)二分法確定左右邊界，然后讓右邊界 - 左邊界 + 1求出答案。

具體思路如下：

先確定右邊界：（讓左下標(biāo)一直往右邊靠）

如果 nums[mid] <= target，就讓?left = mid + 1;

?讓左下標(biāo)一直往右邊走：

?直到走出taget位置，讓右下標(biāo)往右靠：

這樣 left > right?，循環(huán)結(jié)束，找到右邊界left，

特殊情況：

1. 如果數(shù)組內(nèi)不存在target，right所在位置就不是target；

2. 如果數(shù)組不存在target且數(shù)組內(nèi)所以元素都 > target 或者 數(shù)組根本沒(méi)有元素，right就 < 0

也就是right會(huì)跑出數(shù)組，甚至本來(lái)就不在數(shù)組里面，

這兩種情況就直接返回 0 表示不存在 target 值。

接下來(lái)是確定左邊界，我們現(xiàn)將求出的右邊界存下來(lái)：

（讓右下標(biāo)一直往左走）

如果 nums[mid] <?target，就讓?left = mid + 1;

?如果 nums[mid] >=?target，就讓 right?= mid - 1;

?讓右下標(biāo)一直往左走：

?這樣 left > right?，循環(huán)結(jié)束，找到左邊界right，

?最后再讓 右邊界 - 左邊界 + 1 即可，

下面是具體代碼：

代碼：

class Solution {
public:
    int search(vector<int>& nums, int target) {
        //先確定右邊界
        int left = 0, right = nums.size() - 1;
        while(left <= right) {
            int mid = (left + right) >> 1;
            if(nums[mid] <= target) left = mid + 1;
            else right = mid - 1;
        }

        //右邊界如果跑出數(shù)組或者所在位置不等于target，證明數(shù)組內(nèi)沒(méi)有target，就直接返回0
        if(right < 0 || nums[right] != target) return 0;

        //將右邊界存下來(lái)
        int r = right;

        //再確定左邊界
        left = 0, right = nums.size() - 1;
        while(left <= right) {
            int mid = (left + right) >>  1;
            if(nums[mid] < target) left = mid + 1;
            else right = mid - 1;
        }

        //返回：右邊界 - 左邊界 + 1
        return r - left + 1;
    }
};

過(guò)啦！?。?/h3>

寫(xiě)在最后：

以上就是本篇文章的內(nèi)容了，感謝你的閱讀。

如果喜歡本文的話，歡迎點(diǎn)贊和評(píng)論，寫(xiě)下你的見(jiàn)解。

如果想和我一起學(xué)習(xí)編程，不妨點(diǎn)個(gè)關(guān)注，我們一起學(xué)習(xí)，一同成長(zhǎng)。

之后我還會(huì)輸出更多高質(zhì)量?jī)?nèi)容，歡迎收看文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-411931.html

到了這里，關(guān)于【LeetCode】劍指 Offer（27）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！