Alibi

My Life is Getting Better

Leetcode[153, 154] Find Minimum in Rotated Sorted Array

13 Nov 2015

###Task1 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.

###Python

class Solution(object):
    def findMin(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        left = 0
        right = len(nums) - 1
        while left + 1 < right:
            mid = left + (right - left) / 2
            if nums[mid - 1] > nums[mid] and nums[mid + 1] > nums[mid]:
                return nums[mid]
            if nums[mid] > nums[-1]:
                left = mid
            else:
                right = mid
        return min(nums[left], nums[right])

###Java

public class Solution {
    public int findMin(int[] nums) {
        if (nums == null || nums.length == 0) {
        	return -1;
        }

        int left = 0;
        int right = nums.length - 1;

        while (left + 1 < right) {
            if (nums[right] > nums[left]) {
                return nums[left];
            }
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[left]) {
                left = mid;
                continue;
            }
            if (nums[mid] < nums[right]) {
                right = mid;
                continue;
            }
        }

        return nums[left] < nums[right] ? nums[left] : nums[right];
    }
    public static void main(String[] args) {
    	Solution sol = new Solution();
    	int[] nums = {4, 5, 6, 7, 0, 1, 2};
    	System.out.println(sol.findMin(nums));
    }
}

###Java

Find the first one smaller than target(num[end])

``java public class Solution { /** * @param num: a rotated sorted array * @return: the minimum number in the array */ public int findMin(int[] num) { // write your code here if (num == null || num.length == 0) { return 0; } int start = 0; int end = num.length - 1; int target = num[end]; int mid; while (start + 1 < end) { mid = start + (end - start) / 2; if (num[mid] <= target) { end = mid; } else { start = mid; } } return num[start] < num[end] ? num[start] : num[end]; } }


###Points

* BST
* left + 1 < right will guarantee at least three elements, so that mid - 1 or mid + 1 will not over bounds
* check the final results when leaves two

###Task2
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.
  

###Python
```python
class Solution(object):
    def findMin(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        left = 0
        right = len(nums) - 1
        while left + 1 < right:
            mid = left + (right - left) / 2
            if nums[right] > nums[left]:
                return nums[left]
            if nums[mid] > nums[0]:
                left = mid
            elif nums[mid] < nums[0]:
                right = mid
            else:
                left += 1
        return min(nums[left], nums[right])

###Java

public class Solution {
    public int findMin(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }

        int left = 0;
        int right = nums.length - 1;

        while (left + 1 < right) {
            if (nums[right] > nums[left]) {
                return nums[left];
            }
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[left]) {
                left = mid;
                continue;
            } else if (nums[mid] < nums[right]) {
                right = mid;
                continue;
            } else {
                left++;
            }
        }

        return nums[left] < nums[right] ? nums[left] : nums[right];
    }

    public static void main(String[] args) {
    	Solution sol = new Solution();
    	int[] nums = {4, 5, 6, 7, 0, 1, 2};
    	System.out.println(sol.findMin(nums));
    }
}

###Points

Related Posts