Find Minimum in Rotated Sorted Array II -- LeetCode

这道题是Search in Rotated Sorted Array的扩展，思路在Find Minimum in Rotated Sorted Array中已经介绍过了，和Find Minimum in Rotated Sorted Array唯一的区别是这道题目中元素会有重复的情况出现。不过正是因为这个条件的出现，影响到了算法的时间复杂度。原来我们是依靠中间和边缘元素的大小关系，来判断哪一半是不受rotate影响，仍然有序的。而现在因为重复的出现，如果我们遇到中间和边缘相等的情况，我们就无法判断哪边有序，因为哪边都有可能有序。假设原数组是{1,2,3,3,3,3,3}，那么旋转之后有可能是{3,3,3,3,3,1,2}，或者{3,1,2,3,3,3,3}，这样的我们判断左边缘和中心的时候都是3，我们并不知道应该截掉哪一半。解决的办法只能是对边缘移动一步，直到边缘和中间不在相等或者相遇，这就导致了会有不能切去一半的可能。所以最坏情况就会出现每次移动一步，总共移动n此，算法的时间复杂度变成O(n)。代码如下：

public int findMin(int[] num) {
    if(num == null || num.length==0)
        return 0;
    int l = 0;
    int r = num.length-1;
    int min = num[0];
    while(l<r-1)
    {
        int m = (l+r)/2;
        if(num[l]<num[m])
        {
            min = Math.min(num[l],min);
            l = m+1;
        }
        else if(num[l]>num[m])
        {
            min = Math.min(num[m],min);
            r = m-1;
        }
        else
        {
            l++;
        }
    }
    min = Math.min(num[r],min);
    min = Math.min(num[l],min);
    return min;
}

在面试中这种问题还是比较常见的，现在的趋势是面试官倾向于从一个问题出发，然后follow up问一些扩展的问题，而且这个题目涉及到了复杂度的改变，所以面试中确实是一个好题，自然也更有可能出现哈。

Find Minimum in Rotated Sorted Array -- LeetCode

这道题是Search in Rotated Sorted Array的扩展，区别就是现在不是找一个目标值了，而是在bst中找最小的元素。主要思路还是跟Search in Rotated Sorted Array差不多，还是通过左边界和中间的大小关系来得到左边或者右边有序的信息，如果左半边有序，那么左半边最小就是左边第一个元素，可以和当前最小相比取小的，然后走向右半边。否则，那么就是右半半边第一个元素，然后走向左半边。这样子每次可以截掉一半元素，所以最后复杂度等价于一个二分查找，是O(logn)，空间上只有四个变量维护二分和结果，所以是O(1)。代码如下：

public int findMin(int[] num) {
    if(num == null || num.length==0)
        return 0;
    int l = 0;
    int r = num.length-1;
    int min = num[0];
    while(l<r-1)
    {
        int m = (l+r)/2;
        if(num[l]<num[m])
        {
            min = Math.min(num[l],min);
            l = m+1;
        }
        else if(num[l]>num[m])
        {
            min = Math.min(num[m],min);
            r = m-1;
        }
        else
        {
            l++;
        }
    }
    min = Math.min(num[r],min);
    min = Math.min(num[l],min);
    return min;
}

有朋友可能注意到上面的实现还有第三种情况，就是左边界和中间是相等的情况，这道题目其实是不用发生的，因为元素没有重复，而Find Minimum in Rotated Sorted Array II这道题这考虑了元素重复的情况，这里只是为了算法更加一般性，就把那个情况也包含进来，有兴趣的朋友可以看看Find Minimum in Rotated Sorted Array II对重复元素的分析哈。