LeetCode #153 Find Minimum in Rotated Sorted Array 在旋轉後的陣列中找最小值

內容目錄

文章觀看次數: 247

英文原文如下

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

[4,5,6,7,0,1,2] if it was rotated 4 times.
[0,1,2,4,5,6,7] if it was rotated 7 times.

Notice that rotating an array [a[0], a[1], a[2], …, a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], …, a[n-2]].

Given the sorted rotated array nums of unique elements, return the minimum element of this array.

You must write an algorithm that runs in O(log n) time.

中文翻譯

假設一個長度為 n 且依照升冪排列的陣列，並且再旋轉在 1 到 n 次之間。例如，陣列 [0,1,2,4,5,6,7] 可能會變成

[4,5,6,7,0,1,2] 旋轉了4次
[0,1,2,4,5,6,7] 旋轉了7次

請注意，將陣列 [a[0], a[1], a[2], …, a[n-1]] 旋轉 1 次，結果將是 [a[n-1], a[0], a[1], a[2], …, a[n-2]]。

給予一個排序且旋轉過的陣列 nums，其中的元素都是唯一的，回傳陣列中的最小值。

你的解法時間複雜度必須小於等於 O(log n)。

範例及題目限制

解題思路

相信看到那個時間複雜度，大家應該就不會使用 for 迴圈來遍歷整個陣列吧

那樣子時間複雜度肯定就是 O(n)

C# 解決方案

看到這一題，相信熟悉C#的小夥伴肯定就是 LINQ啊

public class Solution {
    public int FindMin(int[] nums) {
        return nums.Min();
    }
}

時間複雜度 : O(n)

可是時間複雜度卻達不到題目要求

當初為了查時間複雜度，還特別去翻找了文件

確實是一個簡單的foreach

方案1 – 二分搜尋法

public class Solution {
    public int FindMin(int[] nums) {
        int li = 0;             //low index
        int hi = nums.Length-1; //high index
      
        while(hi>li)
        {
            int midi = li+(hi-li)/2;
            
            if (nums[midi] < nums[hi]) 
            {
                hi = midi;
            } 
            else 
            {
                li = midi+1;
            }
        }
        
        return nums[li];
    }
}

時間複雜度 : O(log n)

為什麼旋轉後還能使用二分搜尋法呢，這是因為儘管旋轉了，但整個陣列其實還是排序過的!

故還是可以利用中間元素跟最右邊元素來進行判斷，該往哪一邊去切割

Java解決方案

方案1

class Solution {
    public int findMin(int[] nums) {
        int li = 0;             //low index
        int hi = nums.length-1; //high index
      
        while(hi>li)
        {
            int midi = li+(hi-li)/2;
            
            if (nums[midi] < nums[hi]) {
                hi = midi;
            } else {
                li = midi+1;
            }
        }
        
        return nums[li]; 
    }
}

Python3 解決方案

方案1

class Solution:
    def findMin(self, nums: List[int]) -> int:
        li = 0             #low index
        hi = len(nums)-1   #high index
      
        while(hi>li):
            midi = int(li+(hi-li)/2)
            
            if (nums[midi] < nums[hi]):
                hi = midi
            else:
                li = midi+1
     
        return nums[li]

JavaScript 解決方案

方案1

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMin = function(nums) {
    var li = 0;             //low index
    var hi = nums.length-1; //high index

    while(hi>li)
    {
        var midi = parseInt(li+(hi-li)/2,10);

        if (nums[midi] < nums[hi]) 
        {
            hi = midi;
        } 
        else 
        {
            li = midi+1;
        }
    }
    return nums[li]; 
};