leetcode 81. Search in Rotated Sorted Array II 搜尋旋轉排序數組 II(中等)

一、題目大意

标簽: 查找

https://leetcode.cn/problems/search-in-rotated-sorted-array-ii

已知存在一個按非降序排列的整數數組 nums ，數組中的值不必互不相同。

在傳遞給函數之前，nums 在預先未知的某個下标 k（0 <= k < nums.length）上進行了 旋轉 ，使數組變為 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标 從 0 開始 計數）。例如， [0,1,2,4,4,4,5,6,6,7] 在下标 5 處經旋轉後可能變為 [4,5,6,6,7,0,1,2,4,4] 。

給你 旋轉後 的數組 nums 和一個整數 target ，請你編寫一個函數來判斷給定的目标值是否存在于數組中。如果 nums 中存在這個目标值 target ，則傳回 true ，否則傳回 false 。

你必須盡可能減少整個操作步驟。

示例 1：

輸入：nums = [2,5,6,0,0,1,2], target = 0

輸出：true

示例 2：

輸入：nums = [2,5,6,0,0,1,2], target = 3

輸出：false

提示：

• 1 <= nums.length <= 5000
• -104 <= nums[i] <= 104
• 題目資料保證 nums 在預先未知的某個下标上進行了旋轉
• -104 <= target <= 104

進階：

• 這是 搜尋旋轉排序數組 的延伸題目，本題中的 nums  可能包含重複元素。
• 這會影響到程式的時間複雜度嗎？會有怎樣的影響，為什麼？

二、解題思路

即使數組被旋轉過，仍可以使用數組的遞增性，使用二分查找來解決此問題。

使用二分法時，先判斷兩側是否是有序的，哪側是有序的，目前的中點，如果小于等于右端的值說明右側區間是遞增的，反之左區間是遞增的。再判斷目标值是否在有序區間内，如果不在我們可以将左端點向右移一位再繼續二分查找。在有序區間我們繼續在有序區間内進行二分查找。

三、解題方法

3.1 Java實作

public class Solution {
    public boolean search(int[] nums, int target) {
        int l = 0;
        int r = nums.length - 1;
        // 注意：此處是 <=
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] == target) {
                return true;
            }
            // 判斷哪個區間是增序的
            if (nums[l] == nums[mid]) {
                // 判斷不出來，因為有重複數字
                l++;
                // 注意：此處要跳出循環
                continue;
            }
            if (nums[mid] <= nums[r]) {
                // 右區間是增序的
                if (target > nums[mid] && target <= nums[r]) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            } else {
                // 左區間是是增序的
                // 注意：此處是 >=
                if (target >= nums[l] && target < nums[mid]) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
        }
        return false;
    }
}
           

四、總結小記

• 2022/5/27 看到長沙提前進入梅雨季節了，雖然已經離開長沙了還是不經意間關注