算法-之-堆
目录
算法 之 堆
- 堆的好处，每次弹出和装入堆，时间复杂度都是
logn - 支持多个优先级排序，只要你的元素是元组，那么第一个优先级就是
第一个元素，第二个优先级就是第二个元素，以此类推 - 堆：分为小堆和大堆，
但是python中只有小堆的用法，也就是heapq只能支持小堆，如果想用大堆，将元素全部取反即可 - 基本操作：
import heapq
# 默认是小堆
hea = []
# 弹出并返回堆中的最小值，如果堆为空，则不允许弹出
heapq.heappop(hea)
# 往堆中加入元素，并维护为小堆
num = 1
heapq.heappush(hea,num)
# 这里比价好玩的是，判断堆是否为空，其实我们只用判断len(hea)是否等于0基础
1046.最后一块石头的重量
- 使用的是大堆，所以要把元素取反
import heapq
class Solution:
def lastStoneWeight(self, stones: List[int]) -> int:
# 经典的堆的问题
# 但是这个是小根堆，得转化为负数才行
hea = []
for i in stones:
heapq.heappush(hea,-i)
while len(hea) > 1:
y = -heapq.heappop(hea)
x = -heapq.heappop(hea)
if x == y :
continue
else:
heappush(hea,x-y)
print(len(hea))
if len(hea) == 0:
return 0
else:
return -heappop(hea)3264.K次乘运算后的最终数组I
- 入堆的元素，
(nums[i],i),也就是要记录这个下标
import heapq
class Solution:
def getFinalState(self, nums: List[int], k: int, multiplier: int) -> List[int]:
# 找最小值的类型
# 并且还是有顺序的
n = len(nums)
hea = []
for i in range(n):
heapq.heappush(hea,(nums[i],i))
for j in range(k):
num,i = heapq.heappop(hea)
num *= multiplier
nums[i] = num
heapq.heappush(hea,(num,i))
return nums选出和最大的K个元素
观察时间复杂度，发现这个如果是直接暴力的话，时间复杂度是
o ( n 2 ) o(n^2)
o
(
n
2
) ,肯定是超标的，但是如果排序的话，就会破坏掉原本的一个对应的关系，所以考虑绑在一起，然后使用堆来维护
空间为k的一个和值
import heapq
class Solution:
def findMaxSum(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:
# 有几个关键点，一个就是得保留先前的下标，还有就是得匹配nums1 和 nums2 ,然后按照nums1进行排序
n = len(nums1)
# 时间消耗在这里 nlogn
newnums = sorted(zip(nums1,nums2,list(range(n))),key = lambda x:x[0])
ans = [0]*n
# 这样后面可以直接替换
hea = [0]*k
# 现在的任务应该是首先处理一下，就是与当前的元素相同的话，就要先处理
l = 0
# 使用一个变量记录当前的堆的和
s = 0
while l < n:
# 处理完一个元素，然后向后面查找相同的元素，然后再一起加入堆
ans[newnums[l][2]] = s
r = l+1
if r >= n:
break
# 处理元素相同的情况
while r < n and newnums[r][0] == newnums[l][0]:
ans[newnums[r][2]] = ans[newnums[l][2]]
r+=1
# 需要往这个hea里面加入 r - l 个元素
if r >= n:
break
for j in range(l,r):
# 每一次操作就是 logk的时间复杂度
tmp = heapq.heappop(hea)
s -= tmp
if tmp < newnums[j][1]:
heapq.heappush(hea,newnums[j][1])
s += newnums[j][1]
else:
heapq.heappush(hea,tmp)
s += tmp
l = r
return ans
2406.将区间分为最少组数
- 可以看到这个分组的顺序与现在的
排列是无关的，所以我们考虑首先按照区间的左端点进行升序排序 - 考虑实际的分组的模拟操作，我们发现
需要找到当前所有分组当中，右端点最小的区间，如果当前的left<这个最小的right，那么我们就需要重新开一个新的组，如果left>这个最小的right，那么我们就可以更新这个right,考虑使用堆维护
import heapq
class Solution:
def minGroups(self, intervals: List[List[int]]) -> int:
# 可以看到这个划分与实际的挑选的顺序无关，所以我们可以进行先排序处理
intervals.sort(key = lambda x :x[0])
# 接下来就要进行遍历，找到一种数据结构，可以找到最小值并且还能更新的
# 那就考虑使用最小堆
hea = []
for left,right in intervals:
if hea and left > hea[0]:
heapq.heappop(hea)
heapq.heappush(hea,right)
else:
heapq.heappush(hea,right)
return len(hea)重排元素
[模版题] 767.重构字符串
- 总的来说直接参透这个模版即可，模版的功能：就是可以用于构造相邻的元素不同的序列
class Solution:
def reorganizeString(self, s: str) -> str:
# 如果长度是奇数，那么相同的数量不能超过 n//2 + 1
n = len(s)
a = Counter(s).most_common()
m = a[0][1]
if m > n - m +1:
return ""
ans = ['']*n
i = 0
for ch,cnt in a:
for _ in range(cnt):
ans[i] = ch
i += 2
if i >=n:
i = 1 # 从奇数下标开始填
return ''.join(ans)1054.距离相等的条形码
- 模版题目，减少了可行性的判断
class Solution:
def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
n = len(barcodes)
ans = [0]*n
a = Counter(barcodes).most_common()
i = 0
for num ,cnt in a:
for _ in range(cnt):
ans[i] = num
i+=2
if i >= n:
# 从奇数开始
i = 1
return ans第K大/小元素
反悔堆
LCP.30魔塔游戏
import heapq
class Solution:
def magicTower(self, nums: List[int]) -> int:
# 首先判断能否去？其实就统计总和是否》=0即可。
# 在可以到达的时候，最多调整次数为负数的次数
if not sum(nums)>=0:
return -1
# 可以到达
# 其实可以统计一个数的左边最小的负数,包含当前的数
n = len(nums)
cur = 1
hp = []
ans = 0
# 使用小根堆进行存储当前的负数的情况
for i in range(n):
# 负数的话就加入
if nums[i] < 0:
heapq.heappush(hp,nums[i])
# 无论正负，都加入cur
cur+=nums[i]
# 如果栈中还有元素，并且当前没有血量,就弹出反悔最小的负数
while hp and cur <= 0:
p = heapq.heappop(hp)
ans+=1
cur+=abs(p)
return ans