154. Find Minimum in Rotated Sorted Array II

LeetCode 154. Find Minimum in Rotated Sorted Array II

Description

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,4,4,5,6,7] might become:

• [4,5,6,7,0,1,4] if it was rotated 4 times.

• [0,1,4,4,5,6,7] if it was rotated 7 times.

Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given the sorted rotated array nums that may contain duplicates , return the minimum element of this array.

Example 1:

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

Example 2:

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

Constraints:

• n == nums.length

• 1 <= n <= 5000

• -5000 <= nums[i] <= 5000

• nums is sorted and rotated between 1 and n times.

Follow up: This is the same as Find Minimum in Rotated Sorted Array but with duplicates. Would allow duplicates affect the run-time complexity? How and why?

Tags

Array, Binary Search

Solution

Based on the solution for LeetCode 153. Find Minimum in Rotated Sorted Array, we need to consider the case when nums[mid] == nums[end]. We can simply do end--, because though we cannot determine whether the minimum value is on the left side of mid or on the right side, we can remove nums[end] because nums[mid] is a substitute of that.

Complexity

• Time complexity (worst): $O(n)$, if the elements in the array are exactly the same, we need to do for-loop n times.

• Space complexity: $O(1)$

Code

func findMin(nums []int) int {
	start, end := 0, len(nums)-1
	for start+1 < end {
		mid := start + (end-start)/2
		if nums[mid] > nums[end] {
			start = mid
		} else if nums[mid] < nums[end] {
			end = mid
		} else { // 
			end--
		}
	}
	if nums[start] < nums[end] {
		return nums[start]
	}
	return nums[end]
}

Reference

1. 寻找旋转排序数组中的最小值 II