Skip to content
Branch: master
Find file History
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
..
Failed to load latest commit information.
README.md
in.txt
solve.cpp

README.md

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.

Solution

Find Minimum in Rotated Sorted Array I 类似,不过需要考虑a[mid] == a[right]的情况,

此时只需要把right--即可

Code

int findMin(vector<int> &nums) {
	int n = nums.size();
	if (n == 0)
		return INT_MIN;
	int s = 0, t = n - 1;
	while (s < t) {
		if (nums[s] < nums[t])
			return nums[s];
		int mid = (s + t) >> 1;
		if (nums[mid] > nums[t]) {
			s = mid + 1;
		} else if (nums[mid] < nums[t]) {
			t = mid;
		} else {
			t--;
		}
	}
	return nums[s];
}

扩展

Search in Rotated Sorted Array, 从旋转列表中查找某个值

Find Minimum in Rotated Sorted Array

You can’t perform that action at this time.