IOSアルゴリズム(基礎編)---回転配列の最小数字

回転配列(順配列配列開始要素を末尾に移動して形成された配列)の最小値を見つけます.
例:
入力:[4,5,6,1,2,3]出力:1入力:[2,3,3,3,3,0,1]出力:0
この問題はよくアルゴリズムを書く人にとって、とても簡単で、基礎の中の基礎ここで私たちは多種の方法を使って、異なる構想でこの問題を処理します
一:ソート法
構想:配列は順方向に並べ替えて、この時の頭の値は最小で、頭の値を取って出力して、1行のコード、簡潔です
コード#コード#

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

sorted()の時間的複雑さは、Complexity:O(n log n)、where n is the length of the collectionであるため、データが大きい場合に比較的時間がかかる
二:暴力法
構想:forサイクル最小、時間複雑度最小
コード#コード#

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

一度のforの時間の複雑さは:O(n)で、時間のかかることを減らします
方法3:二分法
二分法はこの問題を最善に処理する方法だと思います.
1.最大下付きmax:numbers.count-1,最小下付きmin:0 2.max>minを条件とするwhileサイクル3.中間値midは常に下付き(max+min)/2 4とする.numbers[mid]>numbers[max]説明の最小値がnumbers[mid]の右側にある場合はmin=mid+1を二分し続け、numbers[mid]コード#コード#

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アルゴリズム統合アドレス