https://leetcode.com/problems/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.
You must decrease the overall operation steps as much as possible.
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 problem is similar to Find Minimum in Rotated Sorted Array, but nums may contain duplicates. Would this affect the runtime complexity? How and why?
뭔가 단순해 보여서 Navie하게 풀었는데 통과는 된다.
Leetcode 에선 hard로 책정되어 있던데, Binary Search를 통해서 접근해야 Hard 인 것인가?
1. Python
class Solution:
def findMin(self, nums: List[int]) -> int:
for i in range(1,len(nums)):
if nums[i-1] > nums[i]:
return nums[i]
return nums[0]
근데 저 왼쪽 불기둥이 뜻하는 코드는 ;; return min(nums)... 크흠
당초 문제 출제의도로 여겨지는 Binary Search로 푸는 방법은 아래와 같다.
class Solution:
def findMin(self, nums: List[int]) -> int:
left, right = 0, len(nums) - 1
while left < right:
mid = (left + right) // 2
if nums[mid] > nums[right]:
left = mid + 1
elif nums[mid] < nums[right]:
right = mid
else:
right -= 1
return nums[left]