卖萌的弱渣

I am stupid, I am hungry.

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-Array2.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution(object):
        def findMin(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            l = 0
            r = len(nums)-1

            # l,r 不相等，为了解决[1]的问题
            while l < r:
                m = (l+r)/2
                # m在最小值的左边
                if nums[m] > nums[r]:
                    l = m+1
                # m 在最小值的右边
                elif nums[m] < nums[r]:
                    # m 有可能是答案
                    r = m
                else:
                    return min(self.findMin(nums[:m+1]), self.findMin(nums[m+1:]))
            return nums[l]