153. Find Minimum in Rotated Sorted Array

二刷

把所有情况都讨论了一下然后straight forward地写了一遍

没有一刷的答案好

Runtime: 1 ms, faster than 32.60% of Java online submissions for Find Minimum in Rotated Sorted Array.

Memory Usage: 42.6 MB, less than 44.28% of Java online submissions for Find Minimum in Rotated Sorted Array.

class Solution {

    public int findMin(int[] nums) {

        if (nums == null) {

            throw new IllegalArgumentException();

        }

        int start = 0, end = nums.length - 1;

        

        

        //  0 1 2 3 4 5 6

        // [4,5,6,7,0,1,2]

        //  s           e   mid = 3, nums[mid] = 7

        //          s   e   mid = 5, nums[mid] = 1

        // 

        while (start + 1 < end) {

            int mid = start + (end - start) / 2;

            if (nums[mid] > nums[start]) {

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

                    return nums[start];

                }

                start = mid + 1;

            } else {

                if (nums[mid] > nums[end]) {

                    return nums[end];

                }

                end = mid;

            }

        }

        return Math.min(nums[start], nums[end]);

    }

}

Version checking if mid to end is sorted

Runtime: 1 ms, faster than 32.60% of Java online submissions for Find Minimum in Rotated Sorted Array.

Memory Usage: 42.8 MB, less than 31.17% of Java online submissions for Find Minimum in Rotated Sorted Array.

class Solution {

    public int findMin(int[] nums) {

        // we should check if mid to end is sorted

        // If mid to end is sorted, then the answer is between [start, mid]

        // Otherwise the answer is between [mid + 1, end]

        if (nums == null) {

            throw new IllegalArgumentException();

        }

        int start = 0, end = nums.length - 1;

        while (start + 1 < end) {

            int mid = start + (end - start) / 2;

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

                end = mid;

            } else {

                start = mid + 1;

            }

        }

        return Math.min(nums[start], nums[end]);

    }

}

一刷

Version #3
如果start和end之间是rotated的，那么start就是end的下一个element，应该有start > end
此时的mid 如果大于等于start的话，证明mid落在了start和rotate点之间，此时应该有start=mid+1
如果mid小于start，证明mid落在了rotate点和end之间，此时应该end= mid

反之如果start<end，证明start和end区间是sorted的， 则start就是最小的
100.00 %
class Solution {
    public int findMin(int[] nums) {
        if (nums == null || nums.length == 0) return -1;
        int start = 0, end = nums.length - 1;
        while (start < end) {
            if (nums[start] <= nums[end]) {
                return nums[start];
            }
            int mid = start + (end - start) / 2;
            if (nums[mid] >= nums[start]) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }
        return nums[start];
    }
}

Version #2 Better version
检查后半段是否是sorted
如果后半段是sorted, 则结果在[start, mid]
Time O(logn)
100.00 %
class Solution {
    public int findMin(int[] nums) {
        // Always discard the sorted half
        if (nums == null || nums.length == 0) {
            throw new IllegalArgumentException();
        }
        int start = 0;
        int end = nums.length - 1;
        // start, end
        while (start < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] < nums[end]) { // [mid, end] is sorted
                end = mid;
            } else { // nums[mid] > nums[end]
                start = mid + 1;
            }
        }
        return nums[start];
    }
}



Version #1
检查前半段是否是sorted
这个方法的问题在于如果前半段是sorted, 不能直接舍弃前半段，因为有可能后半段也是sorted, 此时舍弃前半段就是不对的


100.00 %

class Solution {
    public int findMin(int[] nums) {
        // Always discard the sorted half
        if (nums == null || nums.length == 0) {
            throw new IllegalArgumentException();
        }
        int start = 0;
        int end = nums.length - 1;
        // We need at least 3 elements to check
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (nums[start] < nums[mid] && nums[mid] < nums[end]) {
                return nums[start];
            } else if (nums[start] < nums[mid]) { // [start, mid] is sorted
                start = mid + 1;
            } else { // [mid, end] is sorted, nums[mid] < nums[start]
                end = mid;
            }
        }
        return Math.min(nums[start], nums[end]);
    }
}