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) 感谢力扣爸爸 :)