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

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

问题描述

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

uppose 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.

Notice

You may assume no duplicate exists in the array.

Example

Given [4, 5, 6, 7, 0, 1, 2] return 0

解题思路

题目是关于查找在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 原创题目讲解汇总

发表回复

您的电子邮箱地址不会被公开。