【Leetcode】153. Find Minimum in Rotated Sorted Array

Description

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.

You may assume no duplicate exists in the array.

Solution

public int findMin(int[] nums){
        if (nums.length == 1) {
            return nums[0];
        }
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] < nums[i - 1]) {
                return nums[i];
            }
        }
        return nums[0];
    }

Result

AC

Analyse

这个就是用了上一题的思路。

Optimization

First

public int findMin(int[] nums) {
  int low = 0;
  int high = nums.length - 1;
  while (low < high) {
  int mid = low + (high - low) / 2;
  if (nums[mid] < nums[low] && nums[mid] < nums[high] && nums[mid] < nums[mid - 1]) {
  return nums[mid];
  } else {
  if (nums[low] <= nums[mid] && nums[mid] > nums[high] ) {
  //左边还一直在增加,最小的在右边
  low = mid + 1;
  } else{
  //最小的在左边
  high = mid - 1;
  }
  }
  }
  return nums[low];
  }

Second

public int findMin(int[] nums) {
  int low = 0, high = nums.length - 1;
  while (low < high) {
  int mid = low + (high - low) / 2;
  if (nums[mid] < nums[high])
  high = mid;
  else if (nums[mid] > nums[high])
  low = mid + 1;
  }
  return nums[low];
  }

Analyse

这个方法还是使用二分，感觉自己二分还是不够熟练，一定要把每道二分的题都做出来。