找到一個旋轉(zhuǎn)數(shù)組 (正序數(shù)組把起始開始部分元素移到尾部形成的數(shù)組) 的最小值

例如:

輸入: [4, 5, 6, 1, 2, 3] 輸出: 1
輸入: [2, 3, 3, 3, 0, 1] 輸出: 0

這道題對于經(jīng)常寫算法的人來說, 很簡單, 基礎(chǔ)中的基礎(chǔ)
這里我們就用多種方法, 不同思路處理下這個道題

一: 排序法

思路: 數(shù)組正向排序, 此時首值為最小, 取首值輸出即可,
一行代碼, 簡潔

代碼

class Solution {
    func minArray(_ numbers: [Int]) -> Int {
        return numbers.sorted().first!
    }
}

因為sorted()的時間復(fù)雜度是: Complexity: O(n log n), where n is the length of the collection
所以當(dāng)數(shù)據(jù)比較大情況下比較耗時

二: 暴力法

思路: for循環(huán)取最小, 時間復(fù)雜度最小

代碼

class Solution {
    func minArray(_ numbers: [Int]) -> Int {
        var min = numbers.first!
        for i in 0..<numbers.count {
           min = min > numbers[i] ? numbers[i] : min
        }
        return min
    }
}

一次for的時間復(fù)雜度是: O(n), 減少耗時

方法三: 二分法

二分法我認(rèn)為是一種最優(yōu)處理這道題的方法

1.最大下標(biāo)max: numbers.count - 1, 最小下標(biāo)min: 0
2.以max > min為條件while循環(huán)
3.設(shè)置中間值mid 始終下標(biāo)為 (max + min) / 2
4.如果 numbers[mid] > numbers[max] 說明最小值應(yīng)該在numbers[mid]右邊, 令 min = mid + 1 繼續(xù)二分
如果 numbers[mid] < numbers[max] 說明最小值應(yīng)該在numbers[mid]左邊, 令 max = mid 繼續(xù)二分
相等就令 max -= 1, 繼續(xù)二分, 當(dāng)min = max時會跳出循環(huán), 此時 numbers[min]就是我們要找的值

代碼

class Solution {
    func minArray(_ numbers: [Int]) -> Int {
        var min = 0
        var max = numbers.count - 1

        while min < max {
            let mid = (max + min) / 2
            
            if numbers[mid] > numbers[max] {
                min = mid + 1;
            }else if numbers[mid] < numbers[max] {
                max = mid;
            } else {
                max -= 1
            }
        }
        return numbers[min]
    }
}

題目來源：力扣（LeetCode） 感謝力扣爸爸 :)

IOS 算法合集地址