【二分查找专项 】20220320
一、二分查找
时间复杂度：log(N)，也称折半查找。
Leetcode 704
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
链接：https://leetcode-cn.com/problems/binary-search
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
经典二分查找，需要注意的问题：
循环退出条件，注意是 low <= high，⽽不是 low < high
mid 的取值，mid := low + ((high-low)>>1)
low 和 high 的更新。low = mid + 1，high = mid - 1
class Solution:def search(self, nums: List[int], target: int) -> int:# 排除异常if len(nums) == 0: return -1# 左闭右闭left,right = 0,len(nums) - 1# 二分查找while left <= right:mid = left + (right - left) // 2if nums[mid] == target:return midelif nums[mid] > target:right = mid - 1elif nums[mid] < target:left = mid + 1return -1
模板二分查找
参考解析链接：https://www.bilibili.com/video/BV1d54y1q7k7?from=search&seid=10488269091199624753&spm_id_from=333.337.0.0
class Solution:def search(self, nums: List[int], target: int) -> int:if not nums: return -1left,right = -1,len(nums)while left + 1 != right:mid = left + (right - left) // 2if nums[mid] == target:return midelif nums[mid] > target:right = midelif nums[mid] < target:left = midreturn -1
162、寻找峰值
峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞ 。
你必须实现时间复杂度为 O(log n) 的算法来解决此问题。
示例 1：
输入：nums = [1,2,3,1]输出：2解释：3 是峰值元素，你的函数应该返回其索引 2。示例 2：
输入：nums = [1,2,1,3,5,6,4]输出：1 或 5 解释：你的函数可以返回索引 1，其峰值元素为 2； 或者返回索引 5， 其峰值元素为 6。
提示：
1 <= nums.length <= 1000-231 <= nums[i] <= 231 - 1对于所有有效的 i 都有 nums[i] != nums[i + 1]
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/find-peak-element著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
二分查找
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
if not nums: return -1
left,right = 0,len(nums)-1
while left < right:
mid = left + (right - left) // 2
# 满足条件弹出
if nums[mid] > nums[mid + 1] and nums[mid] > nums[mid -1]:
return mid
break
# 仅满足一条 说明峰值在左
if nums[mid] > nums[mid+1]:
right = mid - 1
# 峰值在右
else:
left = mid + 1
return left
正常求解
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
if not nums: return -1
res = 0
for i in range(1,len(nums)):
if nums[i] > nums[res]:
res = i
return res
二分查找简化
两边数组往中间收缩
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
if not nums: return -1
left,right = 0,len(nums)-1
while left < right:
mid = left + (right - left) // 2
if nums[mid] > nums[mid + 1]:
right = mid
else:
left = mid + 1
return left
4、寻找两个正序数组的中位数
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
示例 1：
输入：nums1 = [1,3], nums2 = [2]输出：2.00000解释：合并数组 = [1,2,3] ，中位数 2示例 2：
输入：nums1 = [1,2], nums2 = [3,4]输出：2.50000解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5示例 3：
输入：nums1 = [0,0], nums2 = [0,0]输出：0.00000示例 4：
输入：nums1 = [], nums2 = [1]输出：1.00000示例 5：
输入：nums1 = [2], nums2 = []输出：2.00000
提示：
nums1.length == mnums2.length == n0 <= m <= 10000 <= n <= 10001 <= m + n <= 2000-106 <= nums1[i], nums2[i] <= 106
进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
排序后求中位数
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
nums = nums1 + nums2
nums = sorted(nums)
if len(nums) % 2 == 0:
return (nums[len(nums)//2] + nums[(len(nums)// 2 -1)]) / 2
elif len(nums) % 2 == 1:
return nums[len(nums)//2]
结合冒泡排序
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
nums = nums1 + nums2
# 冒泡排序
for i in range(len(nums)-1):
for j in range(i,len(nums)):
if nums[i] > nums[j]:
nums[i],nums[j] = nums[j],nums[i]
if len(nums) % 2 == 0:
return (nums[len(nums)//2] + nums[(len(nums)// 2 -1)]) / 2
elif len(nums) % 2 == 1:
return nums[len(nums)//2]
二分查找求解
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
# 较短的数组更换为第一个数组，方便后续计算
if len(nums1) > len(nums2):
return self.findMedianSortedArrays(nums2,nums1)
m,n = len(nums1),len(nums2)
# 分割线左边的所有元素需要满足的个数 m + (n -m + 1)/ 2
totalleft = (m+n+1)//2
# 在nums1的区间[0,m]里查找适当的分割线
# 使得nums1[i-1] <= nums2[j] and nums2[j-1] <= nums1[i]
left,right = 0,m
while left < right:
# 如果不加1,在搜索区间只有[i,right]时只有两个元素时会进入死循环
# + 1 下标i-1 就有意义
i = left + (right - left + 1) // 2
j = totalleft - i
if nums1[i-1] > nums2[j]:
# 下一轮搜索区间为[left,i-1]
right = i - 1
elif nums1[i-1] <= nums2[j]:
# 下一轮搜索区间为[i,right]
left = i
infinty = 10**6
i = left
j = totalleft - i
# 定义左右两侧的四个元素
nums1leftmax = -infinty if i == 0 else nums1[i-1] # i=0 时无意义
nums1rightmin = infinty if i == m else nums1[i] # i = m 时无意义
nums2leftmax = -infinty if j == 0 else nums2[j-1] # j = 0 无意义
nums2rightmin = infinty if j == n else nums2[j] # j = n 无意义
# 中位数的表达式
if (m + n) % 2 == 1:
return max(nums1leftmax,nums2leftmax)
else:
return (max(nums1leftmax,nums2leftmax) + min(nums1rightmin,nums2rightmin)) / 2
34、在排序数组中查找元素的第一个和最后一个位置
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
进阶：
你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？
示例 1：
输入：nums = [5,7,7,8,8,10], target = 8输出：[3,4]示例 2：
输入：nums = [5,7,7,8,8,10], target = 6输出：[-1,-1]示例 3：
输入：nums = [], target = 0输出：[-1,-1]
提示：
0 <= nums.length <= 105-109 <= nums[i] <= 109nums 是一个非递减数组-109 <= target <= 109
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
O(N)解法
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
res = []
for i in range(len(nums)):
if nums[i] == target:
res.append(i)
if len(res) == 0:
return [-1,-1]
elif len(res) == 1:
return [res[0],res[0]]
else:
return [res[0],res[-1]]
二分查找解法 O(log n)
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
# 异常值
if len(nums) == 0: return [-1,-1]
left,right = 0,len(nums) - 1
res = []
# 左闭右闭
while left <= right:
mid = left + (right - left) // 2
if nums[mid] > target:
right = mid - 1
elif nums[mid] < target:
left = mid + 1
# 非递减数组 那么一旦找到值，则在左右移动
elif nums[mid] == target:
l = r = mid
while left < l and nums[l-1] == nums[l]:
l -= 1
while right > r and nums[r+1] == nums[r]:
r += 1
# 得到res结果，使用break跳出循环
res = [l,r]
break
# 不存在，返回[-1,-1]
if not res:
return [-1,-1]
return res
模板二分查找
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
if not nums: return [-1,-1]
left,right,res = -1,len(nums),[]
while left + 1 != right:
mid = left + (right - left) // 2
if nums[mid] > target:
right = mid
elif nums[mid] < target:
left = mid
elif nums[mid] == target:
l = r = mid
# l-1 要有意义，left 可能在数组外
while left < l - 1 and nums[l-1] == nums[l]:
l -= 1
while right > r + 1 and nums[r+1] == nums[r]:
r += 1
res = [l,r]
break
if not res: return [-1,-1]
return res
35、搜索插入位置
剑指offerⅡ 68、查找插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例 1:
输入: nums = [1,3,5,6], target = 5输出: 2示例 2:
输入: nums = [1,3,5,6], target = 2输出: 1示例 3:
输入: nums = [1,3,5,6], target = 7输出: 4示例 4:
输入: nums = [1,3,5,6], target = 0输出: 0示例 5:
输入: nums = [1], target = 0输出: 0
提示:
1 <= nums.length <= 104-104 <= nums[i] <= 104nums 为无重复元素的升序排列数组-104 <= target <= 104
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/search-insert-position著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
if not nums: return 0
left,right = -1,len(nums)
while left + 1 != right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
elif nums[mid] > target:
right = mid
elif nums[mid] < target:
left = mid
# [1,2,4,6,8,9] 插入7，返回4，既r的位置
return right
33、搜索旋转排序数组
整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
示例 1：
输入：nums = [4,5,6,7,0,1,2], target = 0输出：4示例 2：
输入：nums = [4,5,6,7,0,1,2], target = 3输出：-1示例 3：
输入：nums = [1], target = 0输出：-1
提示：
1 <= nums.length <= 5000-10^4 <= nums[i] <= 10^4nums 中的每个值都 独一无二题目数据保证 nums 在预先未知的某个下标上进行了旋转-10^4 <= target <= 10^4
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/search-in-rotated-sorted-array著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
暴力遍历求解
class Solution:
def search(self, nums: List[int], target: int) -> int:
for i in range(len(nums)):
if nums[i] == target:
return i
return -1
本题不可使用二分模板，起终点只能限制 数组内下标，而不应该是数组外；【传统二分查找】
class Solution:
def search(self, nums: List[int], target: int) -> int:
if not nums: return -1
left,right = 0,len(nums)-1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
elif nums[mid] <= nums[right]:
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
else:
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
return -1
剑指offer53、在排序数组中查找数字 I
统计一个数字在排序数组中出现的次数。
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8输出: 2示例 2:
输入: nums = [5,7,7,8,8,10], target = 6输出: 0
提示：
0 <= nums.length <= 105-109 <= nums[i] <= 109nums 是一个非递减数组-109 <= target <= 109
注意：本题与主站 34 题相同（仅返回值不同）：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution:
def search(self, nums: List[int], target: int) -> int:
if not nums: return 0
left,right = -1,len(nums)
res = 0
while left + 1 != right:
mid = left + (right - left) // 2
if nums[mid] > target:
right = mid
elif nums[mid] < target:
left = mid
elif nums[mid] == target:
res += 1
l = r = mid
while left < l - 1 and nums[l-1] == nums[l]:
l -= 1
res += 1
while right > r + 1 and nums[r+1] == nums[r]:
r += 1
res += 1
break
return res
剑指offer53 - Ⅱ 0～n-1中缺失的数字
一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
示例 1:
输入: [0,1,3]输出: 2示例 2:
输入: [0,1,2,3,4,5,6,7,9]输出: 8
限制：
1 <= 数组长度 <= 10000
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution:
def missingNumber(self, nums: List[int]) -> int:
left,right = -1,len(nums)
while left + 1 != right:
mid = left + (right - left) // 2
# 如果有mid 说明存在，不在left - mid的区间里，在mid - right里
if nums[mid] == mid:
left = mid
# mid 不相等，则缺失值 在left - mid的这个区间里
else:
right = mid
return right
69、x的平方根
给你一个非负整数 x ，计算并返回 x 的 平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1：
输入：x = 4输出：2示例 2：
输入：x = 8输出：2解释：8 的平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
提示：
0 <= x <= 231 - 1
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/sqrtx著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
二分查找模板
由于一般向下取整，所以返回left
class Solution:
def mySqrt(self, x: int) -> int:
left,right = -1,x + 1
while left + 1 != right:
mid = left + (right - left) // 2
if mid * mid == x:
return mid
elif mid * mid > x:
right = mid
elif mid * mid < x:
left = mid
return left
74、搜索二维矩阵
编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
每行中的整数从左到右按升序排列。每行的第一个整数大于前一行的最后一个整数。
示例 1：
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3输出：true示例 2：
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13输出：false
提示：
m == matrix.lengthn == matrix[i].length1 <= m, n <= 100-104 <= matrixi, target <= 104
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/search-a-2d-matrix著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
数组全数二分查找【二分查找模板】
注意：数字计算得到数组的下标 之和列数有关
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
i = len(matrix)
j = len(matrix[0])
left,right = -1,i*j
# 数组位置的下标 只和列数有关
while left + 1 != right:
mid = left + (right - left) // 2
if matrix[mid//j][mid%j] == target:
return True
elif matrix[mid//j][mid%j] > target:
right = mid
elif matrix[mid//j][mid%j] < target:
left = mid
return False
遍历查找
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
i = len(matrix)
j = len(matrix[0])
for m in range(i):
for n in range(j):
if matrix[m][n] == target:
return True
return False
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
for res in matrix:
if target in res:
return True
return False
左下角开始查找
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
if not matrix or not matrix[0]: return False
# 最大值
rows,cols = len(matrix) - 1, len(matrix[0]) - 1
i,j = rows,0
while i >= 0 and j <= cols:
if matrix[i][j] == target:
return True
elif target > matrix[i][j]:
j += 1
elif target < matrix[i][j]:
i -= 1
return False
81、搜索旋转排序数组 Ⅱ
已知存在一个按非降序排列的整数数组 nums ，数组中的值不必互不相同。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转 ，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。
给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ，则返回 true ，否则返回 false 。
示例 1：
输入：nums = [2,5,6,0,0,1,2], target = 0输出：true示例 2：
输入：nums = [2,5,6,0,0,1,2], target = 3输出：false
提示：
1 <= nums.length <= 5000-104 <= nums[i] <= 104题目数据保证 nums 在预先未知的某个下标上进行了旋转-104 <= target <= 104
进阶：
这是 搜索旋转排序数组 的延伸题目，本题中的 nums 可能包含重复元素。这会影响到程序的时间复杂度吗？会有怎样的影响，为什么？
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/search-in-rotated-sorted-array-ii著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution:
def search(self, nums: List[int], target: int) -> bool:
if not nums: return False
left,right = 0,len(nums)-1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return True
elif nums[mid] <= nums[right]:
if nums[mid] == nums[right]:
right -= 1
elif nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
elif nums[mid] > nums[right]:
if nums[left] == nums[mid]:
left += 1
elif nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
return False
240、搜索二维矩阵Ⅱ
剑指offer04、二维数组的查找
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
每行的元素从左到右升序排列。每列的元素从上到下升序排列。
示例 1：
输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5输出：true
示例 2：
输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20输出：false
提示：
m == matrix.lengthn == matrix[i].length1 <= n, m <= 300-109 <= matrixi <= 109每行的所有元素从左到右升序排列每列的所有元素从上到下升序排列-109 <= target <= 109
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/search-a-2d-matrix-ii著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
无法使用二分查找
class Solution:
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
if not matrix or not matrix[0]: return False
rows,cols = len(matrix) - 1,len(matrix[0])-1
i,j = rows,0
while i >= 0 and j <= cols:
if target == matrix[i][j]:
return True
elif target > matrix[i][j]:
j += 1
elif target < matrix[i][j]:
i -= 1
return False
剑指offer11、旋转数组的最小数字
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。
示例 1：
输入：[3,4,5,1,2]输出：1示例 2：
输入：[2,2,2,0,1]输出：0注意：本题与主站 154 题相同：https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
153、寻找旋转排序数组中的最小值
已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
示例 1：
输入：nums = [3,4,5,1,2]输出：1解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。示例 2：
输入：nums = [4,5,6,7,0,1,2]输出：0解释：原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组。示例 3：
输入：nums = [11,13,15,17]输出：11解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。
提示：
n == nums.length1 <= n <= 5000-5000 <= nums[i] <= 5000nums 中的所有整数 互不相同nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution:
def findMin(self, nums: List[int]) -> int:
left,right = 0,len(nums)-1
while left < right:
mid = left + (right - left) // 2
# if nums[mid] == nums[right]:
# right -= 1
if nums[mid] > nums[right]:
left = mid + 1
elif nums[mid] < nums[right]:
right = mid
return nums[left]
154、寻找旋转排序数组中的最小值Ⅱ
已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,4,4,5,6,7] 在变化后可能得到：若旋转 4 次，则可以得到 [4,5,6,7,0,1,4]若旋转 7 次，则可以得到 [0,1,4,4,5,6,7]注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
给你一个可能存在 重复 元素值的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
示例 1：
输入：nums = [1,3,5]输出：1示例 2：
输入：nums = [2,2,2,0,1]输出：0
提示：
n == nums.length1 <= n <= 5000-5000 <= nums[i] <= 5000nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution:
def minArray(self, numbers: List[int]) -> int:
# 由于无target,mid需要和right比较，无法使用二分模板
left,right = 0,len(numbers) - 1
while left < right:
mid = left + (right - left) // 2
# 递增，mid的右边一定不是最小数字
if numbers[mid] < numbers[right]:
right = mid
# 无法判断mid和right谁小
elif numbers[mid] == numbers[right]:
right = right - 1
# 最小数字在mid~right中，一定不是mid
elif numbers[mid] > numbers[right]:
left = mid + 1
return numbers[left]
167、两数之和Ⅱ - 输入有序数组
给定一个已按照 非递减顺序排列 的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。
函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 1 开始计数 ，所以答案数组应当满足 1 <= answer[0] < answer[1] <= numbers.length 。
你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。
示例 1：
输入：numbers = [2,7,11,15], target = 9输出：[1,2]解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。示例 2：
输入：numbers = [2,3,4], target = 6输出：[1,3]示例 3：
输入：numbers = [-1,0], target = -1输出：[1,2]
提示：
2 <= numbers.length <= 3 * 104-1000 <= numbers[i] <= 1000numbers 按 非递减顺序 排列-1000 <= target <= 1000仅存在一个有效答案
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
dic = {}
for i in range(len(numbers)):
if target - numbers[i] in dic:
return [dic[target-numbers[i]],i + 1]
dic[numbers[i]] = i + 1
二分查找
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
n = len(numbers)
for i in range(n):
left,right = i,n
while left + 1 != right:
mid = left + (right - left) // 2
if target - numbers[i] == numbers[mid]:
return [i+1,mid+1]
elif target - numbers[i] > numbers[mid]:
left = mid
elif target - numbers[i] < numbers[mid]:
right = mid
209、长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
示例 1：
输入：target = 7, nums = [2,3,1,2,4,3]输出：2解释：子数组 [4,3] 是该条件下的长度最小的子数组。示例 2：
输入：target = 4, nums = [1,4,4]输出：1示例 3：
输入：target = 11, nums = [1,1,1,1,1,1,1,1]输出：0
提示：
1 <= target <= 1091 <= nums.length <= 1051 <= nums[i] <= 105
进阶：
如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/minimum-size-subarray-sum著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
暴力解法【超时】
class Solution:
def minSubArrayLen(self, s: int, nums: List[int]) -> int:
res = []
length = float('inf')
for i in range(len(nums)):
for j in range(len(nums) - i):
if sum(nums[i:i+j+1]) >= s:
res.append(nums[i:i+j+1])
length = min(len(nums[i:i+j+1]),length)
if not res: return 0
return length
滑动窗口计算
class Solution:
def minSubArrayLen(self, s: int, nums: List[int]) -> int:
if not nums:
return 0
n = len(nums)
ans = n + 1
# 滑动窗口
start,end = 0,0
total = 0
while end < n:
# 求累加和
total += nums[end]
# 一旦超过累计和，进入判断
while total >= s:
# 计算最小长度
ans = min(ans,end - start + 1)
# total减去起点值
total -= nums[start]
# 起点值+=1
start += 1
end += 1
return 0 if ans == n + 1 else ans
275、H指数Ⅱ
给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数，citations 已经按照 升序排列 。计算并返回该研究者的 h 指数。
h 指数的定义：h 代表“高引用次数”（high citations），一名科研人员的 h 指数是指他（她）的 （n 篇论文中）总共有 h 篇论文分别被引用了至少 h 次。且其余的 n - h 篇论文每篇被引用次数 不超过 h 次。
提示：如果 h 有多种可能的值，h 指数 是其中最大的那个。
请你设计并实现对数时间复杂度的算法解决此问题。
示例 1：
输入：citations = [0,1,3,5,6]
输出：3
解释：给定数组表示研究者总共有 5 篇论文，每篇论文相应的被引用了 0, 1, 3, 5, 6 次。
由于研究者有 3 篇论文每篇 至少 被引用了 3 次，其余两篇论文每篇被引用 不多于 3 次，所以她的 h 指数是 3 。
示例 2：
输入：citations = [1,2,100]
输出：2
提示：
n == citations.length1 <= n <= 1050 <= citations[i] <= 1000citations按 升序排列
二分查找
n - h <= h :其余的
n - h篇论文每篇被引用次数 不超过h次即n - mid > nums[mid] 则继续left = mid + 1
class Solution:
def hIndex(self, citations: List[int]) -> int:
if not citations: return 0
right = n = len(citations)
left = 0
while left < right:
mid = left + (right - left) // 2
if citations[mid] < n - mid:
left = mid + 1
else:
right = mid
return n - left
367、有效的完全平方数
给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。
进阶：不要 使用任何内置的库函数，如 sqrt 。
示例 1：
输入：num = 16输出：true示例 2：
输入：num = 14输出：false
提示：
1 <= num <= 2^31 - 1
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/valid-perfect-square著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
二分查找模板
class Solution:
def isPerfectSquare(self, num: int) -> bool:
left,right = -1,num + 1
while left + 1 != right:
mid = left + (right - left) // 2
if mid * mid == num:
return True
elif mid * mid > num:
right = mid
elif mid * mid < num:
left = mid
return False
投机
class Solution:
def isPerfectSquare(self, num: int) -> bool:
return num ** 0.5 == int(num ** 0.5)
374、猜数字大小
猜数字游戏的规则如下：
每轮游戏，我都会从 1 到 n 随机选择一个数字。请你猜选出的是哪个数字。如果你猜错了，我会告诉你，你猜测的数字比我选出的数字是大了还是小了。你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测结果，返回值一共有 3 种可能的情况（-1，1 或 0）：
-1：我选出的数字比你猜的数字小 pick < num1：我选出的数字比你猜的数字大 pick > num0：我选出的数字和你猜的数字一样。恭喜！你猜对了！pick == num返回我选出的数字。
示例 1：
输入：n = 10, pick = 6输出：6示例 2：
输入：n = 1, pick = 1输出：1示例 3：
输入：n = 2, pick = 1输出：1示例 4：
输入：n = 2, pick = 2输出：2
提示：
1 <= n <= 231 - 11 <= pick <= n
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/guess-number-higher-or-lower著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
二分查找模板
class Solution:
def guessNumber(self, n: int) -> int:
left,right = -1,n + 1
while left + 1 != right:
mid = left + (right - left) // 2
# 猜的mid刚好等于选的值
if guess(mid) == 0:
return mid
# 猜的mid比我选的数字小
elif guess(mid) > 0:
left = mid
# 猜的mid比我选的数字大
elif guess(mid) < 0:
right = mid
return left
441、排列硬币
你总共有 n 枚硬币，并计划将它们按阶梯状排列。对于一个由 k 行组成的阶梯，其第 i 行必须正好有 i 枚硬币。阶梯的最后一行 可能 是不完整的。
给你一个数字 n ，计算并返回可形成 完整阶梯行 的总行数。
示例 1：
输入：n = 5输出：2解释：因为第三行不完整，所以返回 2 。示例 2：
输入：n = 8输出：3解释：因为第四行不完整，所以返回 3 。
提示：
1 <= n <= 231 - 1
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/arranging-coins著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
二分查找模板
class Solution:
def arrangeCoins(self, n: int) -> int:
left,right = -1,n+1
while left + 1 < right:
mid = left + (right - left) // 2
if (mid+1) * mid / 2.0 == n :
return mid
elif (mid+1) * mid / 2.0 < n:
left = mid
elif (mid+1) * mid / 2.0 > n:
right = mid
return left
正常二分查找解法
class Solution:
def arrangeCoins(self, n: int) -> int:
left,right = 1,n
while left <= right:
mid = left + (right - left) // 2
if (mid+1)*mid / 2.0 == n:
return mid
elif (mid+1) *mid/2.0 < n:
left = mid + 1
elif (mid+1) *mid /2.0 > n:
right = mid - 1
return right
暴力解法
class Solution:
def arrangeCoins(self, n: int) -> int:
i = 0
while i < n:
i += 1
n -= i
return i
540、有序数组中的单一元素
给你一个仅由整数组成的有序数组，其中每个元素都会出现两次，唯有一个数只会出现一次。
请你找出并返回只出现一次的那个数。
你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。
示例 1:
输入: nums = [1,1,2,3,3,4,4,8,8]输出: 2示例 2:
输入: nums = [3,3,7,7,10,11,11]输出: 10
提示:
1 <= nums.length <= 1050 <= nums[i] <= 105
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/single-element-in-a-sorted-array著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
二分查找
单一元素一定在偶数坐标！= mid+1的左边
class Solution:
def singleNonDuplicate(self, nums: List[int]) -> int:
left,right = 0,len(nums)-1
while left < right:
# 二分下取整
mid = left + (right - left) // 2
# 奇数再-1
if mid % 2 != 0:
mid -= 1
# 等于说明在右边
if nums[mid] == nums[mid+1]:
# left累加2
left = mid + 2
# 不等于说明在左边
else:
right = mid
return nums[left]
58、最后一个单词的长度
给你一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中 最后一个 单词的长度。
单词 是指仅由字母组成、不包含任何空格字符的最大子字符串。
示例 1：
输入：s = "Hello World"输出：5解释：最后一个单词是“World”，长度为5。示例 2：
输入：s = " fly me to the moon "输出：4解释：最后一个单词是“moon”，长度为4。示例 3：
输入：s = "luffy is still joyboy"输出：6解释：最后一个单词是长度为6的“joyboy”。
提示：
1 <= s.length <= 104s 仅有英文字母和空格 ' ' 组成s 中至少存在一个单词
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/length-of-last-word著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
逆转数组后查询
class Solution:
def lengthOfLastWord(self, s: str) -> int:
s = s[::-1]
res = 0
for i,c in enumerate(s):
if c != ' ':
res += 1
elif c == ' ' and res != 0:
return res
return res
python自带函数strip && split
class Solution:
def lengthOfLastWord(self, s: str) -> int:
return len(s.strip().split(' ')[-1])
541、反转字符串Ⅱ
给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。
如果剩余字符少于 k 个，则将剩余字符全部反转。如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。
示例 1：
输入：s = "abcdefg", k = 2输出："bacdfeg"示例 2：
输入：s = "abcd", k = 2输出："bacd"
提示：
1 <= s.length <= 104s 仅由小写英文组成1 <= k <= 104
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/reverse-string-ii著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution:
def reverseStr(self, s: str, k: int) -> str:
t = list(s)
for i in range(0,len(t),2*k):
t[i:i+k] = t[i:i+k][::-1]
return ''.join(t)
定义反转函数
class Solution:
def reverseStr(self, s: str, k: int) -> str:
t = list(s)
for i in range(0,len(t),2*k):
t[i:i+k] = self.reverselist(t[i:i+k])
return "".join(t)
def reverselist(self,t):
start,end = 0,len(t)-1
while start < end:
t[start],t[end] = t[end],t[start]
start += 1
end -= 1
return t
239、滑动窗口的最大值
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
示例 1：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3输出：[3,3,5,5,6,7]解释：滑动窗口的位置 最大值
[1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7示例 2：
输入：nums = [1], k = 1输出：[1]
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/sliding-window-maximum著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
queue = []
res= []
for i,c in enumerate(nums):
# 删除不在区间里的数
while queue and queue[0] < i-k+1:
queue.pop(0)
# 删除比当前值小的数
while queue and nums[queue[-1]] <= c:
queue.pop()
queue.append(i)
# resappend最大值
res.append(nums[queue[0]])
return res[k-1:]