题目

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.

Subscribe to see which companies asked this question

分析

在含有重复元素的旋转有序序列中查找最小元素。

与上一题类似，LeetCode（153） Find Minimum in Rotated Sorted Array 153题中的旋转有序数组不包含重复元素，而此题允许重复元素，增加了一点难度。

我想题目重点考察的还是沿用二分查找的方法解决，思路参考。

AC代码

class Solution {

public:

    //方法一：使用stl库函数

    int findMin1(vector<int>& nums) {

        if (nums.empty())

            return 0;

        vector<int>::iterator iter = min_element(nums.begin(), nums.end());

        return *iter;

    }

    //方法二：整个数列除一处为最大值到最小值的跳转外，为两部分的递增

    int findMin2(vector<int>& nums)

    {

        if (nums.empty())

            return 0;

        if (nums.size() == 1)

            return nums[0];

        for (size_t i = 1; i < nums.size(); ++i)

        {

            if (nums[i - 1] > nums[i])

                return nums[i];

        }//for

        //没有找到跳转元素，则序列无旋转

        return nums[0];

    }

    int findMin(vector<int> &nums)

    {

        if (nums.empty())

            return 0;

        else if (nums.size() == 1)

            return nums[0];

        else{

            int lhs = 0, rhs = nums.size() - 1;

            while (lhs < rhs && nums[lhs] >= nums[rhs])

            {

                int mid = (lhs + rhs) / 2;

                if (nums[lhs] > nums[mid])

                    rhs = mid;

                else if (nums[lhs] == nums[mid])

                    ++lhs;

                else

                    lhs = mid + 1;

            }//while

            return nums[lhs];

        }

    }

};

GitHub测试程序源码