154. Find Minimum in Rotated Sorted Array II

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:


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];
    }
};

 

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.