154. Find Minimum in Rotated Sorted Array II

Suppose an array sorted in ascending order 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.

Example 1:

Input: [1,3,5]
Output: 1

Example 2:

Input: [2,2,2,0,1]
Output: 0

Note:

• This is a follow up problem to Find Minimum in Rotated Sorted Array.
• Would allow duplicates affect the run-time complexity? How and why?

---

这一题在LeetCode Find Minimum in Rotated Sorted Array的基础上，增加了元素可能重复的约束，此时二分判断时，会出现中间元素和边缘元素相等的情况，此时就不能判断应该丢弃哪半部分了。比如[3,3,1,3]，中间元素3和右边元素3相等，其实应该丢弃左半部分；又比如[1,3,3]，中间元素3和右边元素3相等，其实应该丢弃右半部分。所以遇到中间元素和边缘元素相等时，无法做决定，那么我们只能移动边缘元素，不断的缩小范围，直到中间元素和边缘元素不等。最坏情况是，所有元素都相等时，退化为线性查找了，所以时间复杂度变为了O(n)。
完整代码如下：

class Solution {
public:
    int findMin(vector<int>& nums)
    {
        int l = 0, r = nums.size() – 1;
        while (l < r) {
            int mid = (l + r) / 2;
            if (nums[mid] > nums[r])
                l = mid + 1;
            else if (nums[mid] < nums[r])
                r = mid;
            else
                –r;
        }
        return nums[l];
    }
};

本代码提交AC，用时6MS。

二刷。依然是更加鲁邦容易理解的代码，当nums[mid]==nums[r]时，退化为线性查找。

class Solution {
public:
	int findMin(vector<int>& nums) {
		int l = 0, r = nums.size() - 1;
		int ans = nums[0];
		while (l <= r) {
			if (r - l <= 1) {
				return min(nums[l], nums[r]);
			}
			int mid = l + (r - l) / 2;
			if (nums[mid] > nums[r]) {
				l = mid;
			}
			else if (nums[mid] == nums[r]) {
				--r;
			}
			else {
				r = mid;
			}
		}
		return nums[l];
	}
};

本代码提交AC，用时16MS。