基础算法精讲·题目汇总灵茶山艾府 - 【基础算法精讲】- GitHub视频灵茶山艾府的个人空间-灵茶山艾府个人主页-哔哩哔哩视频二分查找【题单】二分https://leetcode.cn/circle/discuss/SqopEo/04 二分查找 红蓝染色法课程讲解原始二分查找模板代码要求 nums 是非递减的即 nums[i] nums[i1]返回最小的满足 nums[i] target 的 i。如果不存在返回 len(nums)二分查找在闭区间上的写法以及对比开区间、半闭半开区间上的写法≥、target的第一个数、≤、target的最后一个数写法的差别x 等价于 ≥ x1的第一个数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 # [mid1, 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 # [mid1, 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 left1 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 # [mid1, 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, target1) - 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指数等价于求最小最左边的 iclass 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 (leftright) // 2 # n-mid 表示从 mid 到末尾的论文数量 if citations[mid] n-mid: ans n-mid # 满足条件记录答案 right mid-1 # 尝试在左半部分寻找更大的 h else: # 引用次数不够需要在右半部分寻找更大的 h left mid1 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要么是峰顶要么在峰顶右侧因此二分时可以初始化 left0rightn-2n-1一定是蓝色无需再二分可以通过比较 M 和 M1 指向的数字来染色。题目保证了这两个数字一定不相等对于所有有效的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[mid1]: 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[mid1]: # 红色 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 (leftright) // 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. 寻找峰值 II154. 寻找旋转排序数组中的最小值 II