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).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.
自己的代码有错。先找到最小的位置在哪，然后根据target的位置进行遍历
class Solution { public: int search(vector<int>& nums, int target) { int first=0,last=nums.size()-1; if(nums.size()==0) return -1; int realfirst=0,reallast=last; if(nums[first]>nums[last]) { int maxposition=searchmin(nums)-1; if(nums[last]>=target) { realfirst=maxposition+1; } else { reallast=maxposition; } } while(realfirst<reallast) { int middle=(realfirst+reallast)/2; if(target==nums[middle]) return middle; else if(target>nums[middle]) realfirst=middle+1; else if(target<nums[middle]) reallast=middle-1; } if(nums[realfirst]==target) return realfirst; else return -1; } //寻找最小的位置 int searchmin(vector<int>&nums){ int first=0,last=nums.size()-1; int middle=(first+last)/2; while(first<last) if(nums[first]>nums[last]) { if(first+1==last) return last; if(nums[middle]>nums[last]) first=middle; else if(nums[middle]<=nums[last]) last=middle; } else return first; return first; } };别人的方法： class Solution { public: int search(vector<int>& nums, int target) { int lo=0; int hi=nums.size()-1; if(nums.size()==0) return -1; while(lo<hi) { int mid=(lo+hi)/2; if(nums[mid]==target) return mid; if(nums[lo]<=nums[mid])//已经是递增区域.注意这里需要有等号，因为当first==last的时候，循环还是要进行的 { if(target>=nums[lo]&&target<nums[mid]){ hi=mid-1; } else { lo=mid+1; }//不在这个递增区间，转移到另一半 } else//另一半一定是递增区间 { if(target>nums[mid]&&target<=nums[hi])//在这个递增区间内 { lo=mid+1; } else{ hi=mid-1; } } } return nums[lo] == target ? lo : -1; } };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.
You may assume no duplicate exists in the array.
在一个原来排好序的数组中找
class Solution { public: int findMin(vector<int>& nums) { int n=nums.size(); if(n==1) return nums[0]; int left=0; int right=n-1; int mid=0; if(nums[0]<nums[n-1]) return nums[0]; while(true) { mid=left+(right-left)/2; if(left+1==right) { mid=right; break; } if(nums[mid]>nums[left]) left=mid; else if(nums[mid]<nums[right]) right=mid; } return nums[mid]; } };154. Find Minimum in Rotated Sorted Array II 剑 11
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.
如果有重复的数，该怎么办？ class Solution { public: int findMin(vector<int>& nums) { int n=nums.size(); if(n==1) return nums[0]; int left=0; int right=n-1; int mid=0; if(nums[0]<nums[n-1]) return nums[0]; while(true) { mid=left+(right-left)/2; if(left+1==right) { mid=right; break; } if(nums[mid]==nums[left]&&nums[mid]==nums[right]) return doInOrder(nums,left,right); if(nums[mid]>=nums[left]) left=mid; else if(nums[mid]<=nums[right]) right=mid; } return nums[mid]; } int doInOrder(vector<int>& nums,int left,int right){ int res=nums[left]; for(int i=left+1;i<=right;i++) { if(res>nums[i]) res=nums[i]; } return res; } }; 另外一个解答，思路类似： class Solution { public: int findMin(vector<int> &num) { int lo = 0; int hi = num.size() - 1; int mid = 0; while(lo < hi) { mid = lo + (hi - lo) / 2; if (num[mid] > num[hi]) { lo = mid + 1; } else if (num[mid] < num[hi]) { hi = mid; } else { // when num[mid] and num[hi] are same hi--; } } return num[lo]; } };