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.
Example 1:
Input:
[1,3,5]
Output:
1
Example 2:
Input:
[2,2,2,0,1]
Output:
0
Note:
- This is a follow up problem to Find Minimum in Rotated Sorted Array.
- Would allow duplicates affect the run-time complexity? How and why?
Thoughts:
- try binary search first, then go through the ambiguous sections one by one.
My First Draft:
class Solution {
/**
* @param Integer[] $nums
* @return Integer
*/
function findMin($nums) {
$last = count($nums)-1;
$first = 0;
$mid = floor(($last + $first) /2);
$min = null;
while($nums[$first] > $nums[$mid] xor $nums[$mid] > $nums[$last]){
if($nums[$first] > $nums[$mid]){
$last = $mid;
$mid = floor(($last + $first) /2);
} else {
$first = $mid +1;
$mid = floor(($last + $first) /2);
}
}
if($first == $last){
return $nums[$last];
} else {
for($min = $nums[$first];$first <= $last;$first++){
if($nums[$first] < $min){
$min = $nums[$first];
}
}
}
return $min;
}
}
sheehan‘s pretty solution:
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];
}
};