[Leetcode] [Tag 二分法] Python 刷题总结
2019-03-08 本文已影响0人
jl先生
经典的二分法
1. 二分法最经典的写法，其他都是在此基础上的变形。
leetcode 704. Binary Search
Given a sorted (in ascending order) integer array nums of n elements and a target value, write a function to search target in nums. If target exists, then return its index, otherwise return -1.
给定一个有序的数组，如果target存在数组返回target位置，如果不存在返回-1
def search(self, nums, target):
low, high = 0,len(nums) - 1
while low <= high:
mid = low + (high - low) // 2
if nums[mid] == target:
return mid
elif nums[mid] > target:
high = mid - 1
else:
low = mid + 1
return -1
需要注意的地方
整数溢出的情况
这个python不用考虑，主要针对其他语言int类型32位。
稳妥的写法是：
mid = low + (high - low) // 2 # 不同地方在于 high + low 可能会溢出的思想
二分法的变种写法
2. 找出第一个与key相等的元素的位置
这里nums[mid] == target不能立马退出，继续依靠二分法找到target为最优解，每次相等则令high = mid。
def BinarySearch(self, nums, target):
low, high = 0, len(nums) - 1
while low < high: #与经典写法变化的地方
mid = (low + high) // 2
if nums[mid] > target:
high = mid - 1
elif nums[mid] < target:
low = mid + 1
else:
high = mid
if nums[low] == target:
return low
else:
return -1
leetcode 34. Find First and Last Position of Element in Sorted Array
找到最左边和最右边的target
def searchRange(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
if not nums:
return [-1,-1]
low = 0
high = len(nums) - 1
while low <= high:
mid = (low + high) // 1
if nums[mid] > target:
high = mid - 1
elif nums[mid] <= target:
low = mid + 1
low1 = 0
high1 = len(nums) - 1
while low1 <= high1:
mid1 = (low1 + high1) // 1
if nums[mid1] >= target:
high1 = mid1 - 1
elif nums[mid1] < target:
low1 = mid1 + 1
if nums[high] == target and nums[low1] == target:
return [low1,high]
else:
return [-1,-1]
3. 旋转后的有序数组查找
leetcode 33. Search in Rotated Sorted Array
这一题很有意思，O(n)的算法每个人都可以随手写出来，这种题往往分两个区间进行讨论，其中该题首先是判断target在左半边还是又半边，再判断low、high的变化，白板的时候先在草稿纸上演算清楚后free bug应该就不难了。
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
low, high = 0, len(nums)-1
while low <= high:
mid = (low + high) // 2
if nums[mid] == target:
return mid
if nums[low] <= target:
if nums[low] <= nums[mid] < target:
low = mid + 1
else:
high = mid - 1
else:
if target < nums[mid] <= nums[high]:
high = mid - 1
else:
low = low + 1
return -1
leetcode 81. Search in Rotated Sorted Array II
跟leetcode 33差不多，只不过这题可以又重复的数。
def search(self, nums, target):
low, high = 0, len(nums) - 1
while low <= high:
mid = low + (high - low) // 2
if nums[mid] == target:
return True
while nums[low] == nums[mid] and low < mid:
low += 1
if nums[low] <= nums[mid]: #left
if nums[low] <= target < nums[mid]:
high = mid - 1
else:
low = mid + 1
else: #right
if nums[mid] < target <= nums[high]:
low = mid + 1
else:
high = mid - 1
return False
leetcode 69. Sqrt(x)
这道题还蛮有意思的，二分法选择的是从1到x，比暴力快很多。
def mySqrt(self, x):
"""
:type x: int
:rtype: int
"""
if x == 0:
return 0
low, high = 1, x
while low <= high:
mid = (low + high) // 2
if mid*mid <= x and (mid+1)*(mid+1) > x:
return mid
elif mid*mid > x:
high = mid - 1
else:
low = mid + 1
leetcode 74. Search a 2D Matrix
转换成一维数组，思路非常惊喜。
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
if matrix == [[]] or matrix == []:
return False
m, n = len(matrix), len(matrix[0])
low, high = 0,m * n - 1
while low <= high:
mid = (low + high) //2
if matrix[mid//n][mid%n] == target:
return True
elif matrix[mid//n][mid%n] > target:
high = mid - 1
else:
low = mid +1
return False
