Chris's Lab

If you obey all the rules,you miss all the fun.

0%

[LeetCode] 33. Search in Rotated Sorted Array

發表於 分類於 ， ， Disqus：
這題主要運用到二分搜尋法，是 704. Binary Search 的變化題

前言

　　這題主要運用到二分搜尋法，是 704. Binary Search 的變化題，目標是找到一個旋轉陣列中指定元素的陣列，用到一個 while 迴圈和其餘 if 判斷，時間複雜度估 O(log n)，這裡有 JAVA 和 Python 的寫法。

題目

There is an integer array nums sorted in ascending order (with distinct values).
Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].
Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.
You must write an algorithm with O(log n) runtime complexity.

有一個整數陣列 nums 已升序排序 (且具不同的值)。
在傳遞給你的函數之前，nums 可能在一個未知的樞軸索引 k (1 <= k < nums.length) 處旋轉，這樣得到的陣列是 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (索引從0開始)，例如，[0,1,2,4,5,6,7] 可能會在樞軸 3 處旋轉並變成 [4,5,6,7,0,1,2] 。
給定一個可能的旋轉後的陣列 nums 和一個整數 target，如果 target 它在 nums 中就回傳 target 的索引， 如果它不在 nums 中就回傳 -1。
你必須寫出一個 O(log n) 時間複雜度的演算法。

題目連結：https://leetcode.com/problems/search-in-rotated-sorted-array/

題目限制

1 <= nums.length <= 5000
104 <= nums[i] <= 104
All values of nums are unique.
nums is an ascending array that is possibly rotated.
104 <= target <= 104

範例

1
2
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
1
2
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
1
2
Input: nums = [1], target = 0
Output: -1

思路&筆記

這題用的技巧是二分搜尋法，原理是每次循環都會將陣列搜索範圍縮小一半，目的是要找到 target 值的 index

  • 初始我們會設定起點位置、終點位置、中間點 (這些是二分搜尋法的必要條件)
  • middle = start + ( end - start ) / 2 可取得中間點
  • 如果整個陣列都是有序的，那麼目標整數 target 必然存在於該有序的部分，我們可以直接進行二分搜尋找到目標值，但這題比較麻煩的是我們不知道陣列會旋轉成什麼樣子，所以先判斷陣列的左邊還是右邊是否有序
  • 如果那半邊是有序的，就在那半邊使用二分搜尋法做搜尋
  • 如果 target 不在那半邊的話，則會轉向另一邊做搜尋
  • 直到 start 大於等於 end，表示搜尋範圍為空，結束搜尋
  • 到最後範圍會縮到最小，起點值和目標值一定會重疊，然後回傳答案索引

[注意點] 之所以要用上述中間點的寫法會比較安全，因如果 start 和 end 趨近於最大數時，兩者相加起來的合可能會造成整數溢位

JAVA 實現

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    public int search(int[] nums, int target) {

        int start = 0; // 起點位置
        int end = nums.length - 1; // 終點位置

        while (start < end) {

            int middle = start + (end-start)/2; // 中間點
            if (nums[middle] == target) return middle; // 剛好中間點就是答案就回傳

            // 判斷左半邊是有序的
            if (nums[start] <= nums[middle]) {
                // 如果 target 在左半邊的範圍內，則繼續在左半邊進行搜尋
                if (target >= nums[start] && target < nums[middle]) {
                    // 重新定義終點，下次回圈找到新的終點就好
                    end = middle - 1;
                // 否則，轉向右半邊進行搜尋
                } else {
                    // 重新定義起點，下次回圈從新的起點開始就好
                    start = middle + 1;
                }
            // 否則，右半邊是有序的
            } else {
                if (target > nums[middle] && target <= nums[end]) {
                    start = middle + 1;
                } else {
                    end = middle - 1;
                }
            }
        }

        // 到最後範圍會縮到最小，起點值和目標值一定會重疊，就回傳索引
        return nums[start] == target ? start : -1; 
    }
}

Python 實現

使用了和 Java 一樣的邏輯執行，換成 Python 的寫法
不一樣的點是變數的宣告方式不一樣，還有 Java 和 Python 的三元運算寫法不一樣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
    def search(self, nums: List[int], target: int) -> int:

        start, end  = 0, len(nums) - 1 # 起點、終點

        while start < end:
            middle = start + (end - start) // 2 # 中間點

            # 中間點是答案就回傳
            if nums[middle] == target 
                return middle 

                # 判斷左半邊是有序的
                if nums[start] <= nums[middle]:
                    # 如果 target 在左半邊的範圍內，則繼續在左半邊進行搜尋
                    if nums[start] <= target and target < nums[middle]:
                    end = middle - 1
                else: 
                    start = middle + 1 # 否則，轉向右半邊進行搜尋
            # 否則，右半邊是有序的
            else:
                if nums[middle] < target and target <= nums[end]:
                    start = middle + 1
                else:
                    end = middle - 1

        # 如果 start == target 回傳 start 否則回傳 -1
        return start if nums[start] == target else -1

成績

Language Runtime Memory
Java 0ms 41.2MB
Python 54ms 16.75MB