[Swift]LeetCode154. 寻找旋转排序数组中的最小值 II | Find Minimum in Rotated Sorted Array II
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/10059914.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).
Find the minimum element.
The array may contain duplicates.
Example 1:
Input: [1,3,5] Output: 1
Example 2:
Input: [2,2,2,0,1] Output: 0
Note:
- This is a follow up problem to Find Minimum in Rotated Sorted Array.
- Would allow duplicates affect the run-time complexity? How and why?
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
请找出其中最小的元素。
注意数组中可能存在重复的元素。
示例 1：
输入: [1,3,5] 输出: 1
示例 2：
输入: [2,2,2,0,1] 输出: 0
说明：
- 这道题是 寻找旋转排序数组中的最小值 的延伸题目。
- 允许重复会影响算法的时间复杂度吗？会如何影响，为什么？
16ms
1 class Solution {
2 func findMin(_ nums: [Int]) -> Int {
3 var left = 0
4 var right = nums.count - 1
5 while left < right {
6 if nums[left] < nums[right] { return nums[left] }
7 let mid = (left + right) / 2
8 if nums[mid] < nums[left] {
9 right = mid
10 } else if nums[mid] > nums[right] {
11 left = mid + 1
12 } else {
13 right -= 1
14 }
15 }
16 return nums[left]
17 }
18 }52ms
1 class Solution {
2 func findMin(_ nums: [Int]) -> Int {
3 let arraySize = nums.count
4
5 if arraySize == 1 { return nums[0] }
6 if arraySize == 2 { return min(nums[0], nums[1]) }
7 let midElement = arraySize / 2
8 if nums[midElement] > nums[arraySize-1] {
9 return findMin(Array(nums[midElement...arraySize-1]))
10 } else if nums[midElement] < nums[0] {
11 return findMin(Array(nums[0...midElement]))
12 } else {
13 return min(findMin(Array(nums[midElement...arraySize-1])), findMin(Array(nums[0...midElement])))
14 }
15 }
16 }60ms
1 class Solution {
2 func findMin(_ nums: [Int]) -> Int {
3
4 if nums.isEmpty {
5 return -1
6 }
7
8 if nums.count == 1 {
9 return nums[0]
10 }
11
12 var beigin = nums[0]
13 var i = 1
14 while i < nums.count {
15 if nums[i] >= beigin {
16 beigin = nums[i]
17 i += 1
18 } else {
19 return nums[i]
20 }
21 }
22
23 return nums[0]
24 }
25 }76ms
1 class Solution {
2 func findMin(_ nums: [Int]) -> Int {
3 guard nums.count > 0 else { return -1 }
4 return nums.min()!
5 }
6 }