LeetCode Find Minimum in Rotated Sorted Array II

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:


这一题在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。

2 thoughts on “LeetCode Find Minimum in Rotated Sorted Array II

  1. Pingback: LeetCode Search in Rotated Sorted Array II | bitJoy > code

  2. Pingback: 剑指 Offer 11. 旋转数组的最小数字 | bitJoy > code

Leave a Reply

Your email address will not be published. Required fields are marked *