二分
May 7, 2024About 6 min
540. 有序数组中的单一元素 - 力扣（LeetCode）
用 位运算 秒了, 再也不说位运算没用了,但这章的主题是二分,所以还是准备用二分做
class Solution:
def singleNonDuplicate(self, nums: List[int]) -> int:
curr = 0
for i in range(len(nums)):
curr = curr[i]
return curr一个二分法的答案
class Solution:
def singleNonDuplicate(self, nums: List[int]) -> int:
l,r = 0,len(nums)-1
if (len(nums)==1):
return nums[0]
while(l<=r):
mid = (l+r)//2
if(mid==0 and nums[mid+1]!=nums[mid]):
return nums[mid]
if(mid==len(nums)-1 and nums[len(nums)-2]!=nums[mid]):
return nums[mid]
if(nums[mid]!=nums[mid-1]and nums[mid]!=nums[mid+1]):
return nums[mid]
if(nums[mid+1]==nums[mid]):
if((r+1-mid)%2==0):
r=mid-1
else:
l = mid
if(nums[mid-1]==nums[mid]):
if((r-mid)%2==0):
r = mid
else:
l = mid+1
return -1注意模板
这里的 return 条件需要考虑到边界问题
def binarySearch(nums, target):
# 左右都闭合的区间 [l, r]
# A closed interval [l, r] with both ends inclusive.
l, r = 0, len(nums) - 1
while l <= r:
mid = (left + right) >> 1
if nums[mid] == target: return mid
# 搜索区间变为 [mid+1, right]
# Narrow down the search range to [mid+1, right]
if nums[mid] < target: l = mid + 1
# 搜索区间变为 [left, mid - 1]
# Narrow down the search range to [left, mid - 1]
if nums[mid] > target: r = mid - 1
return -134. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）
模板秒杀题, 无难点
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
l, r = 0, len(nums) - 1
if target not in nums:
return [-1, -1]
while l <= r:
mid = (l + r) // 2
if nums[mid] == target:
l_ptr = mid
r_ptr = mid
while l_ptr - 1 >= 0 and nums[l_ptr - 1] == target:
l_ptr -= 1
while r_ptr + 1 < len(nums) and nums[r_ptr + 1] == target:
r_ptr += 1
return [l_ptr, r_ptr]
if nums[mid] > target:
r = mid - 1
if nums[mid] < target:
l = mid + 1
return -1不难发现, 中间用 while 取巧了, 肯定不能这样!
老老实实写了两个
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
def findFirst(nums, target):
l, r = 0, len(nums) - 1
while l <= r:
mid = (l + r) // 2
if nums[mid] >= target:
r = mid - 1
else:
l = mid + 1
if l < len(nums) and nums[l] == target:
return l
return -1
def findLast(nums, target):
l, r = 0, len(nums) - 1
while l <= r:
mid = (l + r) // 2
if nums[mid] <= target:
l = mid + 1
else:
r = mid - 1
if r >= 0 and nums[r] == target:
return r
return -1
left = findFirst(nums, target)
right = findLast(nums, target)
return [left, right]278. 第一个错误的版本 - 力扣（LeetCode）
这道简单题,做的时候却出现了问题
重点是l= mid+1 和 r=mid 的条件为什么是这样?[0,0,0,0,0,0,1,1] 其实是这个样的题, 要求返回第一个 1 的位置,所以右边肯定是不变的, 只用往左边靠,
同理如果要求返回最后一个 0,就会变成 l=mid, r = mid-1 这样的条件
class Solution:
def firstBadVersion(self, n: int) -> int:
if n == 1:
return 1
l, r = 1, n
while l <= r:
mid = (l + r) // 2
if l == r:
return mid
if isBadVersion(mid) == False:
l = mid + 1
if isBadVersion(mid) == True:
r = mid
return -1不是,阿 sir, 你这写的个啥,给我看笑了, 看看正确答案把,看看你的逻辑上的疏忽, 明显下面那个形式更好不是吗 (因为考虑了退出循环的时机)
class Solution:
def firstBadVersion(self, n: int) -> int:
l, r = 1, n
while l <= r:
mid = (l + r) // 2
if isBadVersion(mid) == True:
r = mid - 1
else:
l = mid + 1
return l69. x 的平方根 - 力扣（LeetCode）
一个同样的题,注意模板, 这里为什么要先判断 ==, 可以理解为 [0,0,0,0,1] 模型返回最后一个 0(因为存在余数), 而当没有余数, 刚好相乘等时,需要返回那个 1
class Solution:
def mySqrt(self, x: int) -> int:
l, r = 0, x
while l <= r:
mid = (l + r) // 2
if mid * mid == x:
return mid
if mid * mid > x:
r = mid - 1
else:
l = mid + 1
return r378. 有序矩阵中第 K 小的元素 - 力扣（LeetCode）
没有用到矩阵的性质, 第一个可以优化, 但不重要了
有个问题,写的时候没有想明白, 就是 is_satisfied(mid)<k 的这个更新条件, 之前写的时候用的是 is_satisfied<=k 的这个条件, 然后返回的结果里就会有不在数组中的数, 说明这个地方还是没有想清楚,不是不行,是如果用原来的条件就需要多加个判断.
那么为什么呢?
Info
关于 is_satisfied(mid) < k 与 is_satisfied(mid) <= k
is_satisfied(mid) < k: 此条件检查在矩阵中小于或等于 midmid 的元素数量是否少于 𝑘。如果是，说明第 𝑘 小的元素必须比 mid 大，所以我们需要调整二分搜索的下界 𝑙。此逻辑用于确保我们不会错过第 𝑘 小的元素。is_satisfied(mid) <= k: 如果你原来使用的是这个条件，实际上它会在找到恰好有 𝑘 个元素小于或等于 mid 的情况下停止，但这并不保证 mid 是第 𝑘小的元素，特别是在存在重复元素的情况下。它可能会导致二分查找过早地停止，而错过实际的第 𝑘 小元素。
简单来说就是 is_satisfied 里的 <= 判断已经考虑了重复数的情况了,
class Solution:
def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
def is_satisfied(num):
# given a guess num, return if satisfied
count = 0
for i in range(len(matrix)):
for j in range(len(matrix[0])):
if matrix[i][j] <= num:
count += 1
return count
l, r = matrix[0][0], matrix[len(matrix) - 1][len(matrix) - 1]
while l <= r:
mid = (l + r) // 2
if is_satisfied(mid) < k:
l = mid + 1
else:
r = mid - 1
return l475. 供暖器 - 力扣（LeetCode）
对于每个房屋，要么用前面的暖气，要么用后面的，二者取近的，得到距离
很有想法的一题, 建议多做多思考
class Solution:
def findRadius(self, houses: List[int], heaters: List[int]) -> int:
houses.sort()
heaters.sort()
max_length = 0
for i in range(len(houses)):
insert_num = bisect.bisect_left(heaters, houses[i], 0, len(heaters))
if insert_num == 0:
max_length = max(max_length, heaters[0] - houses[i])
elif insert_num == len(heaters):
max_length = max(max_length, houses[i] - heaters[len(heaters) - 1])
else:
max_length = max(
max_length,
min(
houses[i] - heaters[insert_num - 1],
heaters[insert_num] - houses[i],
),
)
return max_length拿 JS 做了,注意排序要这么排houses.sort((a,b)=>a-b)
用二分的时候，多一个思考方式：
就是插入到哪里，
function bisectLeft(house:number,heater:number[]){
let left = 0;
let right = heater.length;
let mid = Math.floor((left+right)/2);
while(left<right){
mid = Math.floor((left+right)/2);
if(heater[mid]>=house){
right = mid;
}else{
left = mid+1;
}
}
return right;
}875. 爱吃香蕉的珂珂 - 力扣（LeetCode）
class Solution:
def minEatingSpeed(self, piles: List[int], h: int) -> int:
def possible(k):
count = 0
for i in range(len(piles)):
count += piles[i] // k if (piles[i] % k == 0) else piles[i] // k + 1
if count > h:
return False
return True
l, r = 1, max(piles)
while l <= r:
mid = (l + r) // 2
if possible(mid) is False:
l = mid + 1
else:
r = mid - 1
return l778. 水位上升的泳池中游泳 - 力扣（LeetCode）
二分还是帅的, 但是 好像 优先队列 也可以做, 有思路吗?
class Solution:
def swimInWater(self, grid: List[List[int]]) -> int:
def find_max(array):
max_value = 0
for row in array:
for element in row:
if element > max_value:
max_value = element
return max_value
def dfs(x, y, cur_max):
nonlocal is_found
if is_found:
return
if x < 0 or x >= len(grid) or y < 0 or y >= len(grid[0]):
return
if visited[x][y] == 1:
return
if grid[x][y] > cur_max:
return
if x == len(grid) - 1 and y == len(grid[0]) - 1:
is_found = True
return
visited[x][y] = 1
dfs(x - 1, y, cur_max)
dfs(x + 1, y, cur_max)
dfs(x, y + 1, cur_max)
dfs(x, y - 1, cur_max)
return
l = 0
r = find_max(grid)
while l <= r:
visited = [[0] * len(grid) for _ in range(len(grid[0]))]
mid = (l + r) // 2
is_found = False
dfs(0, 0, mid)
if is_found:
r = mid - 1
else:
l = mid + 1
return l