Tuesday, August 25, 2015

Leetcode: Find Minimum in Rotated Sorted Array

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.
You may assume no duplicate exists in the array.
Understand the problem:
The problem looks like the search in rotated sorted array. It is clearly that we need to use the binary search. The key is to decide which half we wanna go in each iteration. There are three cases to consider:
  -- Case 1: nums[lo] < nums[mid] && nums[mid] < nums[hi]. It indicates that the array is sorted. So the first element must be the minimum. So return nums[lo]. 
  -- Case 2: nums[lo] < nums[mid] && nums[mid] > nums[hi]. e.g.. 4 5 6 7 0 1 2. In this case the minimum number must be in the right half. So lo = mid + 1;
  -- Case 3: nums[lo] > nums[mid] && nums[mid] < nums[hi]. e..g. 5 6 7 0 1 2 4. In this case, the minimum must be in the left half, but including the mid. So hi = mid; 
  -- Case 4 (NOT EXISTED): nums[lo] > nums[mid] && nums[mid] > nums[hi]. 7 6 5 4 2 1 0. 
This case does not exist since there is no way to rotate the array like this. 

Code (Java):
public class Solution {
    public int findMin(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        int lo = 0;
        int hi = nums.length - 1;
        
        while (lo + 1 < hi) {
            int mid = lo + (hi - lo) / 2;
            
            if (nums[lo] < nums[mid] && nums[mid] < nums[hi]) {
                return nums[lo];
            }
            
            if (nums[lo] < nums[mid] && nums[mid] > nums[hi]) {
                lo = mid + 1;
            } else if (nums[lo] > nums[mid] && nums[mid] < nums[hi]) {
                hi = mid;
            } 
        }
        
        if (nums[lo] <= nums[hi]) {
            return nums[lo];
        } else {
            return nums[hi];
        }
    }
}

Update on 10/12/15:
public class Solution {
    public int findMin(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        int lo = 0;
        int hi = nums.length - 1;
        
        while (lo + 1 < hi) {
            int mid = lo + (hi - lo) / 2;
            
            if (nums[lo] < nums[hi]) {
                return nums[lo];
            } else if (nums[mid] < nums[hi]) {
                hi = mid;
            } else if (nums[lo] < nums[mid]) {
                lo = mid;
            }
        }
        
        return Math.min(nums[lo], nums[hi]);
    }
}

No comments:

Post a Comment