IOS 算法(基础篇) ----- 旋转数组的最小数字

今天看一道基础的数组算法题

如果你想知道什么题? 既然你诚心诚意的发问了, 我就大发慈悲的告诉你!

找到一个旋转数组 (正序数组把起始开始部分元素移到尾部形成的数组) 的最小值
例如: 输入: [4, 5, 6, 1, 2, 3] 输出: 1
输入: [2, 3, 3, 3, 0, 1] 输出: 0

这道题对于经常写算法的人来说, 很简单, 基础中的基础
这里我们就用多种方法, 不同思路处理下这个道题

方法一: 排序法

思路: 数组正向排序, 此时首值为最小, 取首值输出即可,
一行代码, 简洁

代码

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.count {
           min = min > numbers[i] ? numbers[i] : min
        }
        return min
    }
}

一次for的时间复杂度是: O(n), 减少耗时

方法三: 二分法
二分法我认为是一种最优处理这道题的方法

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] < numbers[max] 说明最小值应该在numbers[mid]左边, 令 max = mid 继续二分
相等就令 max -= 1, 继续二分, 当min = max时会跳出循环, 此时 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 算法合集地址