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.
public class Solution {
public int findMin(int[] num) {
int s = 0;
int e = num.length-1;
if(num[s]<num[e]) return num[s];
while(s<e && num[s]==num[s+1]) s++;
while(s<e && num[e]==num[e-1]) e--;
while(s<=e) {
int m = (s+e)/2;
if(m!=0 && num[m]<num[m-1]) {
return num[m];
}
if(num[s]==num[e]) {
s++;
} else if(num[s]<num[e]) {
return num[s];
} else {
if(num[m]>=num[s]) {
s = m+1;
} else {
e = m-1;
}
}
}
return num[0];
}
}
public class Solution {
public int findMin(int[] num) {
int s = 0;
int e = num.length-1;
if(num[s]<num[e]) return num[s];
while(s<=e) {
int m = (s+e)/2;
if(m!=0 && num[m]<num[m-1]) {
return num[m];
}
if(num[s]<num[e]) {
return num[s];
}
if(num[s]==num[e]) {
if(num[s]>num[0]) s++;
else e--;
} else {
if(num[m]>=num[s]) {
s = m+1;
} else {
e = m-1;
}
}
}
return num[0];
}
}
===============
public class Solution {
public int findMin(int[] num) {
int lo = 0;
int hi = num.length - 1;
int mid = 0;
while(lo <= hi) {
mid = lo + (hi - lo) / 2;
if (num[mid] < num[hi]) {
hi = mid;
}
else if (num[mid] > num[hi]) {
lo = mid + 1;
}
else { // when num[mid] and num[hi] are same
hi--;
}
}
return num[lo];
}
}
没有评论:
发表评论