基础算法精讲·题目汇总：灵茶山艾府 - 【基础算法精讲】- GitHub
视频：灵茶山艾府的个人空间-灵茶山艾府个人主页-哔哩哔哩视频
二分查找
【题单】二分：https://leetcode.cn/circle/discuss/SqopEo/
04 二分查找 红蓝染色法
课程讲解
原始二分查找（模板代码）
要求 nums 是非递减的，即 nums[i] <= nums[i+1]，返回最小的满足 nums[i] >= target 的 i。如果不存在，返回 len(nums)
二分查找在闭区间上的写法，以及对比开区间、半闭半开区间上的写法
≥、＞target（的第一个数）、≤、＜target（的最后一个数）写法的差别
- >x 等价于 ≥ x+1（的第一个数）
- <x 可以看成 ≥ x 的第一个数，它左边的那个数
- ≤x 可以看成 ＞ x 的第一个数，它左边的那个数
红色更新 left 指针，蓝色更新 right 指针
# 左闭右闭 def search(self, nums: List[int], target: int) -> int: left = 0 right = len(nums) - 1 # [left, right] while left <= right: # 区间不为空 mid = (left + right) // 2 # 或写成 left + (right - left) // 2 if nums[mid] < target: left = mid + 1 # [mid+1, right] else: right = mid - 1 # [left, mid-1] return left # 左闭右开 def search(self, nums: List[int], target: int) -> int: left = 0 right = len(nums) # [left, right) while left < right: # 区间不为空 mid = (left + right) // 2 # 或写成 left + (right - left) // 2 if nums[mid] < target: left = mid + 1 # [mid+1, right) else: right = mid # [left, mid) return left # 或 return right 均可 # 左开右开 def search(self, nums: List[int], target: int) -> int: left = -1 right = len(nums) # (left, right) while left+1 < right: # 区间不为空 mid = (left + right) // 2 # 或写成 left + (right - left) // 2 if nums[mid] < target: left = mid # (mid, right) else: right = mid # (left, mid) return right- 由于每次都去掉了一半的元素，时间复杂度为 O(logn)
- 空间复杂度 O(1)，没有用到额外空间
34. 在排序数组中查找元素的第一个和最后一个位置
等于求 target 的开始位置和结束位置，即分别是 ≥ 和 ≤
class Solution: # 左闭右闭版本的模板代码 def search(self, nums, target): left = 0 right = len(nums) - 1 # [left, right] while left <= right: # 区间不为空 mid = (left + right) // 2 # 或写成 left + (right - left) // 2 if nums[mid] < target: left = mid + 1 # [mid+1, right] else: right = mid - 1 # [left, mid-1] return left def searchRange(self, nums: List[int], target: int) -> List[int]: start = self.search(nums, target) # ≥ target的第一个位置 # 如果所有数都 < target 或 这个数不等于target if start == len(nums) or nums[start] != target: return [-1, -1] # ≤ target的最后一个位置，可以转化成 # > target的第一个数，它左边的那个数 # > target等价于 ≥ target + 1 end = self.search(nums, target+1) - 1 # -1表示它左边的那个数 return [start, end]- 时间O(logn)，空间O(1)
课后作业
275. H 指数 II
- 在索引 i 的右侧（包括 i 本身）一共有 n-i 篇论文
- 如果这 n-i 篇论文的引用次数都至少为 citations[i]，即 citations[i] >= n-i（就是一个有效的h指数候选值）
H 指数的定义是：至少有h篇论文，每篇被引用了至少h次。
现在有n-i篇论文。我们令h = n-i。
我们想让这n-i篇论文全都满足“被引用至少n-i次”。
那怎么判断它们全都满足呢？只要这堆论文里最差的那个（也就是 citations[i]）满足就行了
所以，只要citations[i] >= n-i成立，就说明这 n-i 篇论文的引用次数全都 >= n-i
- 求最大的h指数，等价于求最小（最左边）的 i
class Solution: def hIndex(self, citations: list[int]) -> int: # citations[n-h] >= h n = len(citations) left, right = 0, n-1 ans = 0 while left <= right: mid = (left+right) // 2 # n-mid 表示从 mid 到末尾的论文数量 if citations[mid] >= n-mid: ans = n-mid # 满足条件，记录答案 right = mid-1 # 尝试在左半部分寻找更大的 h else: # 引用次数不够，需要在右半部分寻找更大的 h left = mid+1 return ans暂时未做
2529. 正整数和负整数的最大计数
2300. 咒语和药水的成功对数
1385. 两个数组间的距离值
2080. 区间内查询数字的频率
2563. 统计公平数对的数目
875. 爱吃香蕉的珂珂
2187. 完成旅途的最少时间
275. H 指数 II（已做）
2861. 最大合金数
2439. 最小化数组中的最大值
2517. 礼盒的最大甜蜜度
05 数组峰值 搜索旋转排序数组
课程讲解
162. 寻找峰值
找到一个峰顶，大于左右两侧相邻的元素
- 比如下图中的2（第一个2）、4、6（因为可以假设
nums[-1] = nums[n] = -∞）都是峰顶 - 由于峰顶一定在数组中，所以数组最右侧的元素一定是蓝色的（n-1要么是峰顶，要么在峰顶右侧）
- 因此二分时，可以初始化 left=0，right=n-2（n-1一定是蓝色，无需再二分）
- 可以通过比较 M 和 M+1 指向的数字来染色。题目保证了这两个数字一定不相等（对于所有有效的
i都有nums[i] != nums[i + 1]），所以要么小于，要么大于 - 若是小于，说明 M 在峰顶左侧（M右侧存在峰顶），都是红色，更新left
- 若是大于，说明 M 要么是峰顶，要么在峰顶右侧（M左侧存在峰顶），都是蓝色，更新right
- 二分循环结束后，L就是答案（左闭右闭写法时）
# 左闭右闭写法 class Solution: def findPeakElement(self, nums: List[int]) -> int: # [0, n-2] left, right = 0, len(nums)-2 while left <= right: mid = (left + right) // 2 if nums[mid] < nums[mid+1]: left = mid + 1 else: right = mid - 1 return left # 左开右开写法 class Solution: def findPeakElement(self, nums: List[int]) -> int: # [0, n-2] # (-1, n-1) left, right = -1, len(nums)-1 while left + 1 < right: mid = (left + right) // 2 if nums[mid] < nums[mid+1]: # 红色 left = mid else: # 蓝色 right = mid return right- 时间O(logn)，空间O(1)
153. 寻找旋转排序数组中的最小值
给你一个数组，它可能是一个递增的数组，也有可能是两段递增数组且第一个数 > 最后一个数。如何用O(logn) 的时间找到数组的最小值？
- 需要一个判定方式来判断 nums[mid]（即二分的位置）是在最小值的左侧还是右侧
- 可以和最后一个数比大小。由于最小值一定在数组中，那么最后一个数要么是最小值，要么在最小值的右侧。因此 n-1 一定是蓝色
- 因此，在 0 ~ n-2 中二分
- 如果 nums[mid] < 最后一个数，那么 nums[mid] 所处的位置有两种情况：在一段递增数组中，或者在两段递增数组中的第二段。无论是哪种情况，nums[mid] 要么是最小值，要么在最小值右侧。染成蓝色
- 如果 nums[mid] > 最后一个数，那么 nums[mid] 只可能在两段递增数组中，且一定在最小值左侧（第一段）。染成红色
class Solution: def findMin(self, nums: List[int]) -> int: # [0, n-2] # (-1, n-1) left, right = -1, len(nums)-1 while left + 1 < right: mid = (left + right) // 2 if nums[mid] > nums[-1]: # 红色 left = mid else: # 蓝色 right = mid return nums[right]33. 搜索旋转排序数组
【力扣-Python-33】搜索旋转排序数组（middle）
找 target（可能不在数组中），需要在 [0, n-1] 上二分，有两种做法：
- 参考153题，首先找到最小值，然后比较 target 和最后一个数的大小，来判断在哪段二分查找 target。需要两次二分
- 可以只一次二分。分三种情况讨论，什么时候nums[mid] 在 target 及其右侧（染成蓝色）
- 如果二分的位置 > 最后一个数，说明在第一段。如果此时 target 也大于最后一个数，说明 target 也在第一段。且如果 nums[mid] >= target，说明在 target 及其右侧，染成蓝色
- 如果二分的位置 ≤ 最后一个数，说明在第二段。如果此时 target 大于最后一个数，说明 target 在第一段。直接就说明 nums[mid] 在 target 及其右侧（染成蓝色）
- 如果二分的位置 ≤ 最后一个数，说明在第二段。target 也在第二段，nums[mid] >= target，这种情况也是蓝色
- 其余情况就是红色
class Solution: def is_blue(self, nums, i, target): end = nums[-1] if nums[i] > end: return target > end and nums[i] >= target else: return target > end or nums[i] >= target # [0, n-1] # (-1, n) def search(self, nums: List[int], target: int) -> int: left, right = -1, len(nums) while left + 1 < right: mid = (left + right) // 2 if self.is_blue(nums, mid, target): right = mid else: left = mid if right == len(nums) or nums[right] != target: return -1 return right课后作业
74. 搜索二维矩阵
【力扣-Python-74】搜索二维矩阵（middle）
（整体二分）整个矩阵行内有序，行间也有序，可以把这个二维矩阵想象成一个一维的有序数组
- 定义一个映射关系，对于一维索引，用整除列数得到行号，用取余列数得到列号
- 即：一维索引 index —> 二维行号 = index // n，二维列号 = index % n
- 有了这个映射，就可以直接对整个矩阵进行一次二分查找
class Solution: def searchMatrix(self, matrix: list[list[int]], target: int) -> bool: m, n = len(matrix), len(matrix[0]) left, right = 0, m*n-1 while left <= right: mid = (left+right) // 2 row, col = mid // n, mid % n if matrix[row][col] == target: return True elif matrix[row][col] < target: left = mid + 1 else: right = mid - 1 return False暂时未做
1901. 寻找峰值 II
154. 寻找旋转排序数组中的最小值 II
