【力扣hot100】刷题笔记Day20
前言
- 今天学习了一句话“自己如果不努力，屎都吃不上热乎的”，话糙理不糙，与君共勉
35. 搜索插入位置 - 力扣（LeetCode）
-
二分查找
-
class Solution:def searchInsert(self, nums: List[int], target: int) -> int:n = len(nums)l, r = 0, n - 1while l <= r: # 左闭右闭mid = l + (r - l) // 2if nums[mid] == target:return midelif nums[mid] < target:l = mid + 1else:r = mid - 1return r + 1 # 应该插入的位置
-
74. 搜索二维矩阵 - 力扣（LeetCode）
-
二分查找
-
class Solution:def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:m, n = len(matrix), len(matrix[0])l, r = 0, m * n - 1while l <= r:mid = l + (r - l) // 2row = mid // n # 转化成矩阵中的行坐标col = mid % n # 转化成矩阵中的列坐标print(mid, row, col)if matrix[row][col] < target: l = mid + 1elif matrix[row][col] > target:r = mid - 1else:return Truereturn False
-
34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）
-
二分查找（左右边界）
-
class Solution:def searchRange(self, nums: List[int], target: int) -> List[int]:# 寻找[target,...,target]的左边界def leftBorder(nums, target):l, r = 0, len(nums) - 1while l <= r:mid = l + (r - l) // 2if nums[mid] >= target:r = mid - 1else:l = mid + 1return l# 寻找[target,...,target]的右边界def rightBorder(nums, target):l, r = 0, len(nums) - 1while l <= r:mid = l + (r - l) // 2if nums[mid] <= target:l = mid + 1else:r = mid - 1return rl_Border = leftBorder(nums, target)r_Border = rightBorder(nums, target)if l_Border <= r_Border:return [l_Border, r_Border]else: # 排除找不到target的情况return [-1, -1]
-
-
二分查找（单边界滑动）
-
class Solution:def searchRange(self, nums: List[int], target: int) -> List[int]:# 寻找[target,...,target]的左边界def leftBorder(nums, target):l, r = 0, len(nums) - 1while l <= r:mid = l + (r - l) // 2if nums[mid] >= target:r = mid - 1else:l = mid + 1return ln = len(nums)l_Border = leftBorder(nums, target)# 处理特殊情况，找不到targetif l_Border == n or nums[l_Border] != target: return [-1,-1]# 允许范围内，右边界向右滑动r_Border = l_Borderwhile r_Border + 1 <= n - 1 and nums[r_Border+1] == target:r_Border += 1return [l_Border, r_Border]
-
33. 搜索旋转排序数组 - 力扣（LeetCode）
-
二分查找（寻找有序）
-
class Solution:def search(self, nums: List[int], target: int) -> int:n = len(nums)l, r = 0, n - 1while l <= r:mid = l + (r - l) // 2# mid左侧（包含mid）为有序部分，一个元素nums[0]==nums[mid]也有序，所以要<=if nums[0] <= nums[mid]:if nums[0] <= target < nums[mid]:r = mid - 1elif target == nums[mid]:return midelse:l = mid + 1# mid右侧（包含mid）为有序部分else:if nums[mid] < target <= nums[n - 1] :l = mid + 1elif target == nums[mid]:return midelse:r = mid - 1 return -1
-
153. 寻找旋转排序数组中的最小值 - 力扣（LeetCode）
-
二分查找（寻找无序）
-
class Solution:def findMin(self, nums: List[int]) -> int:l, r = 0, len(nums) - 1while l <= r:mid = l + (r - l) // 2# 左边有序，右边无序，去右边找if nums[0] <= nums[mid]: # <=，考虑[2,1]中l=mid情况，要往右找if mid > 0 and nums[mid-1] > nums[mid]: # 异常递减值return nums[mid]else:l = mid + 1# 右边有序，左边无序，去左边找else:if mid > 0 and nums[mid-1] > nums[mid]: # 异常递减值return nums[mid]else:r = mid - 1return nums[0] # 找不到说明无旋转，nums[0]就是最小# 简洁优化，边界难处理 class Solution:def findMin(self, nums: List[int]) -> int:l, r = 0, len(nums) - 1if nums[l] <= nums[r]: # 本身有序返回第一个return nums[l]while l <= r:mid = l + (r - l) // 2if nums[0] <= nums[mid]: # <=，考虑[2,1]中l=mid情况，要往右找l = mid + 1 # 右边无序往右找else: r = mid - 1 # 左边无序往左找return nums[l]
-
4. 寻找两个正序数组的中位数 - 力扣（LeetCode）
- 困难题，要递归找两个有序数组的第k大数，看思路讲解和代码实现
-
class Solution:def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:"""给定两个排好序的数组，求他们合并后的第k大数"""def findK(nums1, nums2, k):if len(nums1) == 0: # 其中一个为空就返回另一个的第k大，对应下标k-1return nums2[k-1]if len(nums2) == 0:return nums1[k-1] if k == 1: # 第1大就比较头两个数return min(nums1[0], nums2[0])k1 = min(k//2, len(nums1)) # 划分给nums1的数量，可能不够k2 = min(k-k1, len(nums2)) # 剩余给nums2的数量，可能不够if nums1[k1-1] < nums2[k2-1]: # 小的数不可能是第k大了，删除后递归去下一层return findK(nums1[k1:], nums2, k-k1)else: # 由于可能有不够的现象，相等不意味着就是第k大，还要继续分割return findK(nums1, nums2[k2:], k-k2)size = len(nums1) + len(nums2)if size % 2 == 0: # 偶数left = findK(nums1, nums2, size // 2) # 10就是找第5right = findK(nums1, nums2, size // 2 + 1) # 10就是找第6res = (left + right) / 2else: # 奇数res = findK(nums1, nums2, size // 2 + 1) # 11就是找第6return res
后言
- 二分实现和记模板不难，主要是要处理好边界，多在草稿上演算一下就行