LeetCode 解题报告 (33,81,153,154)-- 二分搜索找旋转数组特定值

发表于 标签 ，

本文主要讲述如何在一个 Rotated Sorted Array 中找到特定的值，Rotated Sorted Array 指旋转了的数组，如 4 5 6 7 0 1 2 就是 0 1 2 4 5 6 7 的一个旋转数组。正常情况下遍历一遍即可，但是这样的时间复杂度为 \(O(n)\), 但是本文主要讲述通过二分查找将时间复杂度降到 \(O(log_2n)\)。

本文主要以 LeetCode 上的四道题目为例讲解，分别是

33. Search in Rotated Sorted Array
81. Search in Rotated Sorted Array II
153. Find Minimum in Rotated Sorted Array
154. Find Minimum in Rotated Sorted Array II

其中 33、81 是在 Rotated Sorted Array 找出给定的值，不同的地方在于 33 中没有重复元素，而 81 中有重复的元素；153、154 则是在 Rotated Sorted Array 中找到最小值，区别也是一个有重复元素而另一个没有。

33. Search in Rotated Sorted Array

对于一个 Rotated Sorted Array，每次的 binary search 查找的中间元素都会将原来的 list 分为两个 lists, 其中的一个 list 肯定是有序的，可以判断目标元素是否在这个有序的 list 中，如果在这个 list 则在这个 list 内进行二分查找，否则在另外一个 list 内找。

这种方法时间复杂度为 \(O(log_2n)\)。实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution(object):  
    def search(self, nums, target):  
        """  
        :type nums: List[int]  
        :type target: int  
        :rtype: int  
        """  
        if len(nums) == 0:  
            return -1  
        left = 0  
        right = len(nums) - 1

        while left < right:  
            mid = (left + right)/2  
            if nums[mid] == target:  
                return mid

            if nums[left] <= nums[mid]:  
                if nums[left]<=target<=nums[mid]:  
                    right = mid - 1   # mid要减去1，否则两个元素的时候会导致死循环  
                else:  
                    left = mid+1

            if nums[mid] <= nums[right]:  
                if nums[mid]<=target<=nums[right]:  
                    left = mid + 1  
                else:  
                    right = mid - 1

        if nums[left] == target:  
            return left  
        else:  
            return -1

81. Search in Rotated Sorted Array II

这个问题的解决思路同上面的类似，但是因为有可能存在重复的元素，所以每次 binary search 后分成的两个 lists 中不一定存在一个有序的 list， 这时候就需要两个 list 都遍历了，所以这种方法最差情况下的时间复杂度为 O(n)。

实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution(object):  
    def search(self, nums, target):  
        """  
        :type nums: List[int]  
        :type target: int  
        :rtype: bool  
        """  
        if len(nums) == 0:  
            return False  
        n = len(nums)  
        if self.helper(nums, 0, n-1,target):  
            return True  
        else:  
            return False


    def helper(self,nums,left,right,target):  
        if left > right:  
            return False  
        if left == right:  
            return nums[left] == target  
        else:  
            mid = (left+right)/2  
            if nums[mid] == target:  
                return True  
            elif  nums[left]<=target<nums[mid]:  
                return self.helper(nums,left,mid-1,target)  
            elif nums[mid]<target<=nums[right]:  
                return self.helper(nums,mid+1,right,target)  
            else:  
                return self.helper(nums,mid+1,right,target) or self.helper(nums,left,mid-1,target)

153. Find Minimum in Rotated Sorted Array

本题需要求 Rotated Sorted Array 中最小的元素，且 Rotated Sorted Array 中没有重复元素。关键点在于每次将 nums[(left+right)/2] 与 nums[right] 比较，假如 nums[(left+right)/2]>nums[right], 则最小值在 nums[(left+right)/2:right] 中，反之在另一半元素中。

实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):  
    def findMin(self, nums):  
        """  
        :type nums: List[int]  
        :rtype: int  
        """  
        if len(nums) == 0: return None  
        left, right = 0, len(nums)-1  
        while left < right:  
            mid = (left+right)/2  
            if nums[right] < nums[mid]:  
                left = mid + 1  
            else:  
                right = mid  
        return nums[left]

通过找到最小元素，也可以解决上面提到的问题 33. Search in Rotated Sorted Array，就是先用二分搜索找到最小元素的下标，最小元素的下标会将原来的 list 分为两个 sorted list，判断 target 在哪个 sorted list 然后对这个 sorted list 进行二分查找即可。

这种方法对 array 进行了两次二分查找

实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution(object):  
    def search(self, nums, target):  
        """  
        :type nums: List[int]  
        :type target: int  
        :rtype: int  
        """  
        if len(nums) == 0:  
            return -1  
        left = 0  
        right = len(nums)-1  
        while left<right:  
            mid = (left+ right)/2  
            if nums[mid]>nums[right]:  
                left = mid + 1  
            else:  
                right = mid  
        minIndex = left

        if minIndex == 0:  
            if nums[minIndex]<=target<= nums[len(nums)-1]:  
                return self.binarySearch(minIndex,len(nums)-1,nums,target)  
            else:  
                return -1  
        else:  
            if nums[0]<= target<=nums[minIndex-1]:  
                return self.binarySearch(0,minIndex-1,nums,target)  
            elif nums[minIndex]<= target<=nums[len(nums)-1]:  
                return self.binarySearch(minIndex,len(nums)-1,nums,target)  
            else:  
                return -1

    # 对一个sorted list的经典二分查找  
    def binarySearch(self,left,right,nums,target):  
        while left < right:  
            mid = (left + right)/2  
            if nums[mid] == target:  
                return mid  
            elif nums[mid]>target:  
                right = mid -1  
            else:  
                left = mid+1  
        if nums[left] == target:  
            return left  
        else:  
            return -1

154. Find Minimum in Rotated Sorted Array II

这个问题跟 153. Find Minimum in Rotated Sorted Array不同的地方是 Rotated Sorted Array 中可能存在重复的元素，虽然也可以通过二分搜索解决，但是最差的情况下的时间复杂度也是 O(n), 最差的情况下就是 nums[left]=nums[mid]=nums[right], 这是无法确定最小元素在那一边，因此两边都要搜索。下面给出两种实现方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
# method 1  
class Solution(object):  
    def findMin(self, nums):  
        """  
        :type nums: List[int]  
        :rtype: int  
        """  
        if len(nums) == 0: return None  
        left, right = 0, len(nums)-1  
        while left < right:  
            mid = (left+right)/2  
            if nums[right] < nums[mid]:  
                left = mid + 1  
            elif nums[right] > nums[mid]:  
                right = mid  
            else:  
                if nums[mid] == nums[left]:  
                    if sum(nums[left:mid+1]) == nums[mid] * (mid-left+1):  
                        left = mid + 1  
                    else:  
                        right = mid  
                else:  
                    right = mid  
        return nums[left]

# method 2  
class Solution(object):  
    def findMin(self, nums):  
        """  
        :type nums: List[int]  
        :rtype: int  
        """  
        if len(nums) == 0: return None  
        left, right = 0, len(nums)-1  
        while left < right:  
            mid = (left+right)/2  
            if nums[right] < nums[mid]:  
                left = mid + 1  
            elif nums[right] > nums[mid]:  
                right = mid  
            else:  
                right -= 1  
        return nums[left]