Find Minimum in Rotated Sorted Array I
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.
思路:
当nums[left]<nums[right],说明数组没有旋转,是按升序排列的。可直接返回nums[left];
当nums[left]<nums[mid],说明left至mid这段是按升序排列的,可令left=mid+1;
当nums[left]>nums[mid],说明mid至right这段是按升序排列的,可令right=mid;
理清思路后,代码就变的异常简单了,下面的代码不是按照这个思路来的,这个思路是写II的时候才想出来的,用这个思路来写的话,非常好理解。
class Solution { public: int findMin(vector<int> &num) { int len=num.size(); int Left,Right,Mid; Left=0; Right=len-1; while(Left<=Right) { Mid=Left+(Right-Left)/2; if(num[len-1]<num[Mid]) Left=Mid+1; else Right=Mid-1; } return num[Left]; } };
Find Minimum in Rotated Sorted Array II
Follow up for "Find Minimum in Rotated Sorted Array":
What if duplicates are allowed?Would this affect the run-time complexity? How and why?
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.
The array may contain duplicates.
这个思路和1差不多,关键是怎么处理重复的元素。
代码中continue那个语句是亮点。
class Solution { public: int findMin(vector<int>& nums) { int len=nums.size(); int left=0; int right=len-1; int mid=0; while(left<right) { if(nums[left]==nums[right]) { left++; continue; } if(nums[left]<nums[right]) //这一步其实才是最大的亮点啊,解决了left=mid+1所带来的困惑,而且更加的高效 return nums[left]; mid=(left+right)/2; if(nums[mid]>=nums[left]) left=mid+1; else right=mid; } return nums[left]; } };