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 | class Solution(object): |
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
31class 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
15class 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
47class 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 | # method 1 |