现在的位置: 首页 > 综合 > 正文

leetcode——Find Minimum in Rotated Sorted Array II

2018年04月12日 ⁄ 综合 ⁄ 共 1129字 ⁄ 字号 评论关闭

题目:


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

The array may contain duplicates.



思路:

本题思路跟“没有重复元素”的情况相似。当没有重复元素的时候,首先判断首元素和末元素大小关系。如果首元素小于末尾元素,则不用分析,一定是顺序排列的,返回第一个就是最小的。否则,寻找中间位置的值,若中间位置值大于第首元素,则最小值一定在右边的一半数组中;否则在左边一半的数组中。
当有重复元素时,在比较首元素和末元素的时候先要去重保证两元素不等,并对坐标关系进行判断(如果首末的位置最终到了同一个位置,则整个数组都是同一个值)这样才能知道排列趋势。
在非顺序排列的情况下,进行比较:如果mid和start的元素一样,则start++直到变成该值的最后一个的位置。
如果mid和end一样,则end--直到变成该值的第一个值;不用考虑start位置上的值==end位置上的值的情况。
注意:
如何知道最终结果是哪个?在while循环中的条件应该是只剩两个元素,也就是start<end-1,这时,当start=end-1的时候就会停止,最小值一定在这两个中(二分法锁定的最终结果)。

AC代码:

public int findMin(int[] num) {
        if (num == null)
            return 0;
        if (num.length == 1)
            return num[0];
        int i = 0;
        for (i = num.length - 1; i >= 0 && num[i] == num[0]; i--) ;
        if (i == -1)
            return num[0];


        int start = 0, end = i, mid = 0;
        if (num[start] < num[end]) {
            return num[start];
        } else {
            while (start < end-1) {
                mid = (start + end) >> 1;
                if (num[start] == num[mid]) {
                    for (start = mid + 1; start < end && num[start] == num[mid]; start++) ;
                    start--;
                } else if (num[end] == num[mid]) {
                    for (end = mid - 1; end > start && num[end] == num[mid]; end--) ;
                    end++;
                } else {
                    if (num[mid] < num[start])
                        end = mid;
                    else
                        start = mid;
                }
            }
        }
        return num[end]>num[start]?num[start]:num[end];
    }


抱歉!评论已关闭.