[劍指-Offer] 53. I. 在排序數組中查找數字 I 及 II. 0～n-1中缺失的數字(二分法、代碼優化、巧妙解法)

文章目錄

• • 1. 題目來源
  • 2. 題目說明
  • 3. 題目解析 --- I. 在排序數組中查找數字 I
  • • 方法一：周遊+正常解法
    • 方法二：二分法+遞歸+巧妙解法
  • 4. 題目解析 --- II. 0～n-1中缺失的數字
  • • 4.1 方法一：周遊+正常解法
    • 方法二：二分法+巧妙解法

1. 題目來源

連結：I. 在排序數組中查找數字 I

連結：II. 0～n-1中缺失的數字

來源：LeetCode——《劍指-Offer》專項

2. 題目說明

3. 題目解析 — I. 在排序數組中查找數字 I

方法一：周遊+正常解法

順序周遊即可。時間複雜度 O ( n ) O(n) O(n)，空間複雜度 O ( 1 ) O(1) O(1)。沒有用到 排序數組 的特性。

參見代碼如下：

// 執行用時 :4 ms, 在所有 C++ 送出中擊敗了98.65%的使用者
// 記憶體消耗 :15.8 MB,在所有 C++ 送出中擊敗了100.00%的使用者

class Solution {
public:
    int search(vector<int>& nums, int target) {
        if (nums.size() == 0) return 0;
        int tmp = 0;
        for (int i = 0; i <nums.size(); ++i) {
            while (i < nums.size() and nums[i] == target) {
                ++tmp;
                ++i;
            }
        }
        return tmp;;
    }
};
           

方法二：二分法+遞歸+巧妙解法

二分法的巧妙應用，現以找連續出現數字的第一個位置為例，主要思路如下：

• 每次拿中間數字

  nums[mid]

  與

  target

  做比較
  • 若

    nums[mid] > target

    則

    target

    隻能出現在前半段，即

    right = mid - 1

  • 若

    nums[mid] < target

    則

    target

    隻能出現在前半段，即

    left = mid + 1

  • 若

    nums[mid] == target

    ，首先需要判斷中間這個數字是不是第一個

    target

    ，如果中間數字的前一個數字不等于

    target

    那麼中間數字就是第一個

    target

    ，如果前一個數字也為

    target

    那麼第一個數字出現的位置就在前半段，是以

    right = mid - 1

至此，即可采用二分+遞歸的思想解決這個問題了，關于最後一個

target

的位置查找與上面的思想基本一緻，在此不列出，可自行思考。

時間複雜度 O ( l o g n ) O(logn) O(logn)，空間複雜度 O ( 1 ) O(1) O(1)

是以，遇到排序數組或者能轉化成排序數組的形式，二分法是降低時間複雜度的利器！

參見代碼如下：

// 執行用時 :16 ms, 在所有 C++ 送出中擊敗了22.43%的使用者
// 記憶體消耗 :23.7 MB, 在所有 C++ 送出中擊敗了100.00%的使用者

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = getLeft(nums, target, 0, nums.size() - 1);
        int right = getRight(nums, target, 0, nums.size() - 1);
        if (left > -1 and right > -1) return right - left + 1;
        return 0; 
    }

    int getLeft(vector<int> nums, int target, int left, int right) {
        if (left > right) return -1;
        int mid = (left + right) >> 1;
        if (nums[mid] == target) {
            if ((mid > 0 and nums[mid - 1] != target) or mid == 0) return mid;
            else right = mid - 1;
        }
        else if (nums[mid] > target) right = mid - 1;
        else left = mid + 1;

        return getLeft(nums, target, left, right);
    }

    int getRight(vector<int> nums, int target, int left, int right) {
        if (left > right) return -1;
        int mid = (left + right) >> 1;
        if (nums[mid] == target) {
            if ((mid < nums.size() - 1 and nums[mid + 1] != target) or mid == nums.size() - 1) return mid;
            else left = mid + 1;
        }
        else if (nums[mid] < target) left = mid + 1;
        else right = mid - 1;

        return getRight(nums, target, left, right);
    }
};
           

4. 題目解析 — II. 0～n-1中缺失的數字

4.1 方法一：周遊+正常解法

暴力法，周遊數組，數字在數組中，其下标與目前數組所存放的值相同，若不相同，則傳回數組下标即可。若周遊完數組仍為傳回，說明數組有序，最後一個數字是缺失數字，則需要傳回數組末尾存放的數字再加一即可。時間複雜度 O ( n ) O(n) O(n)，空間複雜度 O ( 1 ) O(1) O(1)。

// 執行用時 :24 ms, 在所有 C++ 送出中擊敗了58.30%的使用者
// 記憶體消耗 :19.5 MB, 在所有 C++ 送出中擊敗了100.00%的使用者
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        for (int i = 0; i < nums.size(); ++i) {
            if (i != nums[i]) 
                return i;
        }
        return nums.back() + 1;
    }

};
           

方法二：二分法+巧妙解法

類比在有序數組查找某數是否存在一個性質。

參見代碼如下：

// 執行用時 :20 ms, 在所有 C++ 送出中擊敗了82.48%的使用者
// 記憶體消耗 :19.5 MB, 在所有 C++ 送出中擊敗了100.00%的使用者

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int left = 0, right = nums.size();
        while (left < right) {
            int mid = (left + right) >> 1;
            if (mid == nums[mid]) left = mid + 1; 
            else right = mid;
        }
        return left;
    }
};