LintCode 159. Find Minimum in Rotated Sorted Array 原创Java参考解答

问题描述

http://www.lintcode.com/en/problem/find-minimum-in-rotated-sorted-array/

解题思路

题目是关于查找在Rotated Sorted Array(RST)一种已按大小排序但被旋转过的数列里面的最小元素。

通过题目给出的例子，可以看到这种数列的特点是由小变大，到了某一个位置可能会突然下降，然后再次逐渐由小变大。值得注意的是数列如[1, 2, 3] 其实也算作rotated sorted array，它假定只是把第一个元素和自己做位置调换。

对于找一个数列中的位置或者某个数字的题目，一般来讲用Binary Search二分法。

这道题同样可以运用二分法解决。初始化时候start = 0，end = 0。

• 当二分得到的中间位置的数值 < end位置的数值时候，把end 更新为 mid。其他情况即中间位置的数值 > end位置时候，中间位置的数值一定在rotated数列中的第一次数字上升部分，这时把start更新为mid。
• 二分循环后，只剩下首尾两数时候，如果start位置的数字 < end 位置的数字，则返回start位置的数字。反之，则返回end位置的数字。

参考代码

public class Solution { 
    /** 
     * @param nums: a rotated sorted array 
     * @return: the minimum number in the array 
     */ 
    public int findMin(int[] nums) { 
        if (nums == null || nums.length == 0) { 
            return 0; 
        } 
         
        int start = 0; 
        int end = nums.length - 1; 
         
        while (start + 1 < end) { 
            int mid = start + (end - start) / 2; 
            if (nums[mid] > nums[end]) { 
                start = mid; 
            } else { 
                end = mid; 
            } 
        } 
 
        if (nums[start] < nums[end]) { 
            return nums[start]; 
        } else { 
            return nums[end]; 
        } 
    } 
}

相关题目

LintCode All in One 原创题目讲解汇总