首页 > 代码库 > leetcode-Find Minimum in Rotated Sorted Array-153
leetcode-Find Minimum in Rotated Sorted Array-153
一个递增数组，没有重复的元素，可能被右移过，找出最小的元素
这和这题差不多http://www.cnblogs.com/0summer/p/5825282.html
依旧是改进过的二分：
1.如果nums[l]<nums[mid]，说明[l,mid]是递增的，但是[mid,r]不确定
1）如果nums[mid]>nums[r]说明[mid,r]包括了递增数组的首尾，那么最小值一定在这个区间，则l=mid+1；
2）否则最小值在[l,mid]区间，则r=mid-1
2.如果nums[l]>nums[mid]，说明[l,mid]包括了递增数组的首尾，那么最小值一定在这个区间，则r=mid-1
3.nums[l]=nums[mid]说明此时l==mid，则l++
1 class Solution { 2 public: 3 int findMin(vector<int>& nums) { 4 if(nums.size()==0) return 0; 5 int l=0,r=nums.size()-1; 6 int key=INT_MAX; 7 //int cnt=1; 8 while(l<=r){ 9 //cout<<cnt++<<endl;10 int mid=(l+r)>>1;11 if(nums[mid]<=key){12 key=nums[mid];13 }14 if(nums[l]<nums[mid]){15 if(nums[mid]>nums[r]) l=mid+1;16 else r=mid-1;17 }18 else if(nums[l]>nums[mid]){19 r=mid-1;20 }21 else l++;22 }23 return key;24 }25 };
leetcode-Find Minimum in Rotated Sorted Array-153
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。