[LeetCode]154.Find Minimum in Rotated Sorted Array II

【题目】

Follow up for "Find Minimum in Rotated Sorted Array":
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

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.

【分析】

这一道题是上一道题的拓展延伸：[LeetCode]153.Find Minimum in Rotated Sorted Array

上一道题目说明没有重复数字，这一道题目添加上了这一要求，有了重复数字。

因此这一道题目比上一道题目多了些特殊情况：

我们看一组例子：｛1，0，1，1，1｝ 和 ｛1，1，1，0，1｝ 都可以看成是递增排序数组｛0，1，1，1，1｝的旋转。

这种情况下我们无法继续用上一道题目的解法，去解决这道题目。因为在这两个数组中，第一个数字，最后一个数字，中间数字都是1。

第一种情况下，中间数字位于后面的子数组，第二种情况，中间数字位于前面的子数组。

因此当两个指针指向的数字和中间数字相同的时候，我们无法确定中间数字1是属于前面的子数组（绿色表示）还是属于后面的子数组（紫色表示）。

也就无法移动指针来缩小查找的范围。

【代码】

/*********************************
*   日期：2015-01-31
*   作者：SJF0115
*   题目: 154.Find Minimum in Rotated Sorted Array II
*   网址：https://oj.leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/
*   结果：AC
*   来源：LeetCode
*   博客：
**********************************/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int findMin(vector<int> &num) {
        int left = 0,right = num.size() - 1;
        int mid = 0;
        // num[left] >= num[right] 确保旋转
        while(num[left] >= num[right]){
            // 分界点
            if(right - left == 1){
                mid = right;
                break;
            }//if
            mid = left + (right - left) / 2;
            // num[left] num[right] num[mid]三者相等
            // 无法确定中间元素是属于前面还是后面的递增子数组
            // 只能顺序查找
            if(num[left] == num[right] && num[left] == num[mid]){
                return MinOrder(num,left,right);
            }//if
            // 中间元素位于前面的递增子数组
            // 此时最小元素位于中间元素的后面
            if(num[mid] >= num[left]){
                left = mid;
            }//if
            // 中间元素位于后面的递增子数组
            // 此时最小元素位于中间元素的前面
            else{
                right = mid;
            }
        }//while
        return num[mid];
    }
private:
    // 顺序寻找最小值
    int MinOrder(vector<int> &num,int left,int right){
        int result = num[left];
        for(int i = left + 1;i < right;++i){
            if(num[i] < result){
                result = num[i];
            }//if
        }//for
        return result;
    }
};

int main(){
    Solution solution;
    //vector<int> num = {0,1,2,3,4,5};
    vector<int> num = {1,0,1,1,1,1,1};
    int result = solution.findMin(num);
    // 输出
    cout<<result<<endl;
    return 0;
}

【代码二】

class Solution {
public:
    int findMin(vector<int> &num) {
        int left = 0,right = num.size() - 1;
        int mid = 0;
        while(left < right){
            mid = left + (right - left) / 2;
            if(num[mid] > num[right]){
                left = mid + 1;
            }//if
            else if(num[mid] < num[right]){
                right = mid;
            }//else
            // 不能确定最小元素在哪边
            else{
                --right;
            }
        }//while
        return num[left];
    }
};