[Swift]LeetCode154.寻找旋转排序数组中的最小值II|FindMinimuminRotatedSortedArrayI ...

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/10059914.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

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 }