leetcode hard : Find Minimum in Rotated Sorted Array I, II

https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/

Find Minimum in Rotated Sorted Array II - LeetCode

 

이거 전 문제를 푼거같은데 들어가보니까 제출기록이 없네 어찌된 일이지? (https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/description/)

class Solution:
    def findMin(self, nums):
        left, right = 0, len(nums)-1
                
        while left < right:
            mid = (left + right) // 2
                        
            if nums[mid] > nums[right]:
                left = mid + 1
            else:
                right = mid

        return nums[left]

mid가 가리키는게 right가 가리키는거보다 크면 left를 mid+1로 올려버린다.

그니까 left가 가리키는건 right가 가리키는것보다 작다는게 반드시 보장된다.

left랑 right가 같은 상태에서 else조건에 걸리면 무한루프가 걸리기 때문에 while조건엔 등호가 없는 <를 사용했다. <=가 아니라.

mid가 가리키는게 right가 가리키는거랑 같거나 작으면 right는 mid랑 같은걸 가리키게 자꾸 내려온다.

결국 left는 nums[-1]보다 작거나 같은 요소중에 제일 왼쪽에 있는 요소를 가리키게되고 이것은 rotated sorted array의 original array의 시작점을 의미한다.

 

이제 문제2로 넘어가보자.

기본적인 요구사항은 문제1과 같다. 근데 follow-up이 눈에 띈다

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?

문제1은 모든 요소가 unique했지만 이건 duplicates를 포함할 수 있다는 얘기다. 문제를 푸는 것도 중요하지만 이게 runtime complexity에 영향을 끼칠까?를 생각해봐야한다.

결론부터 말하자면 난 영향이 있다고 생각한다.

 

극단적인 경우

[2,2,2,2,2,2,2,2,2,2,1,2,2,2,2,2]

문제1의 솔루션을 적용하면 답이 안나온다.

mid가 가리키는게 right가 가리키는거보다 작거나 같으면 자꾸 right를 내리게 되어있어서 첫 loop때 바로 right가 1이 있는 위치보다 낮아지게된다.

이런 경우도 있을 수 있다.

[2,2,2,2,1,2,2,2,2,2,2,2,2,2,2,2,2]

 

맨 처음 loop때 left도 2를 가리키고 mid도 2를 가리키고 right도 2를 가리키는데 left를 올릴지 right를 내릴지 어떻게 결정할 수 있을까?

결정할 수 없다. 주어진 정보가 불충분하다. 이럴때는 linear scan을 해야한다. 그래서 duplicates가 많으면 runtime complexity에 영향을 끼친다. 괜히 db에서 index가 되는 key는 중복이 적고 range가 넓은 컬럼을 선택하는게 아니다!!!

 

그래서 mid랑 right가 가리키는 값이 같으면 right를 1씩 내리도록 약간의 변화를 가해 문제를 풀면 된다.

class Solution:
    def findMin(self, nums):
        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]

복잡도는

공간은 당연히 O(1)이고

시간의 경우

데이터의 분포가 잘 퍼져있을수록 O(log N)

중복 데이터가 많아질수록 O(N)에 가까워질 확률이 높아진다.