首页 > 代码库 > 153. Find Minimum in Rotated Sorted Array

153. Find Minimum in Rotated Sorted Array

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.

开始做的时候,想出了一种用treeset做的方法,代码如下:

<style>p.p1 { margin: 0.0px 0.0px 0.0px 0.0px; font: 12.0px "Helvetica Neue"; color: #454545 }</style>

public class Solution {

    public int findMin(int[] nums) {

        TreeSet<Integer> set = new TreeSet<Integer>();

        int min = Integer.MAX_VALUE;

        for(int i=0;i<nums.length;i++){

            Integer floor = set.floor(nums[i]);

            if(floor!=null){

                min = Math.min(min,floor);

            }

            set.add(nums[i]);

        }

        min = Math.min(min,nums[nums.length-1]);

        return min;

    }

}

但是时间复杂度是NlogN,后来又用二分查找做出来的,二分查找通常是在原数组已经排好序的时候使用:

<style>p.p1 { margin: 0.0px 0.0px 0.0px 0.0px; font: 12.0px "Helvetica Neue"; color: #454545 }</style>

public class Solution {

    public int findMin(int[] nums) {

        int left= 0;

        int right = nums.length-1;

        while(left<right){

            if(nums[left]<nums[right]) return nums[left];

            int mid = left+(right-left)/2;

            if(nums[mid]<nums[left]){

                right = mid;

            }else{

                left = mid+1;

            }

        }

        return nums[left];

    }

}

本题可以省略if(nums[left]<nums[right]) return nums[left];的步骤,就是以将mid和右面进行比较,代码如下:

<style>p.p1 { margin: 0.0px 0.0px 0.0px 0.0px; font: 12.0px "Helvetica Neue"; color: #454545 }</style>

public class Solution {

    public int findMin(int[] nums) {

        int left = 0;

        int right = nums.length-1;

        for(int i=0;i<nums.length;i++){

            int mid = left+(right-left)/2;

            if(nums[mid]<nums[right]){

                right = mid;

            }else if(nums[mid]>nums[right]){

                left = mid+1;

            }

        }

        return nums[left];

    }

}

他们之间的区别可以通过一个例子看出来nums = {1,3},对于第一种解法,如果不加入if(nums[left]<nums[right]) return nums[left];那么mid的值就是和left相等的,这种情况是无法排除出去的。而对于第二种情况,mid的性质是一直在前半部分赋值,意思是如果是两个元素,那么mid就是第一个元素;如果是三个元素,那么是中间的元素。所以mid永远不可能和right是相等的,所以不需要考虑mid=right的情况。

153. Find Minimum in Rotated Sorted Array