携手创作，共同成长！这是我参加「日新计划 8 月更文应战」的第15天，点击检查活动概况

前语

咱们社区陆续会将顾毅（Netflix 增长黑客，《iOS 面试之道》作者，ACE 工作健身教练。）的 Swift 算法题题解收拾为文字版以方便咱们学习与阅览。

LeetCode 算法到现在咱们已经更新到 152 期，咱们会保持更新时刻和进度（周一、周三、周五早上 9:00 发布），每期的内容不多，咱们希望咱们能够在上班路上阅览，持久堆集会有很大提高。

不积跬步，无以致千里；不积小流，无以成江海，Swift社区 伴你前行。假如咱们有建议和意见欢迎在文末留言，咱们会尽力满意咱们的需求。

难度水平：中等

1. 描述

已知一个长度为 n 的数组，预先依照升序摆放，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在改变后或许得到：

  • 若旋转 4 次，则能够得到 [4,5,6,7,0,1,2]
  • 若旋转 7 次，则能够得到 [0,1,2,4,5,6,7]

注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的成果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

给你一个元素值 互不相同 的数组 nums ，它原来是一个升序摆放的数组，并按上述景象进行了屡次旋转。请你找出并返回数组中的 最小元素 。

你必须设计一个时刻复杂度为 O(log n) 的算法处理此问题。

2. 示例

示例 1

输入：nums = [3,4,5,1,2]
输出：1
解说：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。

示例 2

输入：nums = [4,5,6,7,0,1,2]
输出：0
解说：原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组。

示例 3

输入：nums = [11,13,15,17]
输出：11
解说：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。

约束条件：

  • n == nums.length
  • 1 <= n <= 5000
  • -5000 <= nums[i] <= 5000
  • nums 中的一切整数 互不相同
  • nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转

3. 答案

class FindMinimumRotatedSortedArray {
    func findMin(_ nums: [Int]) -> Int {
        var minVal = Int.max
        var left = 0
        var right = nums.count - 1
        while left <= right {
            let mid = (right - left) / 2 + left
            if nums[mid] >= nums[left] {
                minVal = min(minVal, nums[left])
                left = mid + 1
            } else {
                minVal = min(minVal, nums[mid])
                right = mid - 1
            }
        }
        return minVal
    }
}
  • 首要思维：经典的二叉搜索。
  • 时刻复杂度： O(logn)
  • 空间复杂度： O(1)

该算法题解的库房：LeetCode-Swift

点击前往 LeetCode 操练

关于咱们

咱们是由 Swift 爱好者共同保护，咱们会分享以 Swift 实战、SwiftUI、Swift 根底为中心的技能内容，也收拾搜集优异的学习材料。

后续还会翻译很多材料到咱们大众号，有感爱好的朋友，能够加入咱们。