描述
Suppose a sorted array 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.
You may assume no duplicate exists in the array.
分析
寻找旋转排序数组中的最小值,最差的情况是 $O(n)$,一次遍历就行了。用二分法是更好的做法,判断的条件是左边的值大于右边的值,这时要找的这个值一定在左右两个数的中间,这时的时间复杂度是 $O(lg(n))$
解决方案1(Python)
蛮力法:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
| class Solution(object): def findMin(self, nums): """ :type nums: List[int] :rtype: int """ nums_len = len(nums) if nums_len == 1: return nums[0] for i in range(nums_len-1): if(nums[i+1]<nums[i]): return nums[i+1] return nums[0]
|
二分法:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
| class Solution(object): def findMin(self, nums): """ :type nums: List[int] :rtype: int """ nums_len = len(nums) if nums_len == 1: return nums[0] left = 0 right = nums_len - 1 while(nums[left] > nums[right]): mid = (left + right) / 2 if nums[mid] > nums[right]: left = mid + 1 else : right = mid return nums[left]
|
解决方案2(C++)
蛮力法:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
| class Solution { public: int findMin(vector<int>& nums) { int len = nums.size(); if(len == 1) { return nums[0]; } for(int i = 1; i < len; i++) { if(nums[i] < nums[i-1]) { return nums[i]; } } return nums[0]; } };
|
二分法:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
| class Solution { public: int findMin(vector<int>& nums) { int len = nums.size(); if(len == 1) { return nums[0]; } int left = 0, right = len-1; while(nums[left] > nums[right]) { int mid = (left + right) / 2; if(nums[mid] > nums[right]) { left = mid + 1; }else { right = mid; } } return nums[left]; } };
|
解决方案3(Golang)
二分法。
1 2 3 4 5 6 7 8 9 10 11 12
| func findMin(nums []int) int { low, high := 0, len(nums) - 1 for low < high { mid := low + (high-low) / 2 if nums[mid] < nums[high] { high = mid } else { low = mid + 1 } } return nums[low] }
|
相关问题