LeetCode 2462 雇佣 K 位工人的总代价
1. 题目
自己的思路
自己的思路比较原始，一开始想着通过python前后切片，找出前后2个candidate里最小的元素，然后用remove来删除第一个出现的最小值元素就可以了。结果样例出现了错误，bug的原因是通过remove来删除最小值元素，删除的可能不是前后两个candidate的元素，而是中间未遍历到的元素，删除后列表元素的顺序就乱套了。
后来自己进行了改进，在前后切片的时候记录最小值的下标，这样就能用pop删除指定下标的元素。代码如下：
class Solution:
def totalCost(self, costs: List[int], k: int, candidates: int) -> int:
res = 0
length = len(costs)
for i in range(k):
front_min_val = min(costs[:candidates])
front_min_idx = costs[:candidates].index(front_min_val)
behind_min_val = min(costs[-candidates:])
behind_min_idx = costs[-candidates:].index(behind_min_val)
if front_min_val<= behind_min_val:
i_min_cost = front_min_val
i_min_idx = front_min_idx
else:
i_min_cost = behind_min_val
i_min_idx = length - candidates + behind_min_idx
length -= 1
res += i_min_cost
costs.pop(i_min_idx)
return res结果超时了。分析后发现，每次循环的复杂度是$O(candidate+n)$，k次循环的复杂度是$ O(k * (candidates + n/2))$，总体复杂度可以简化为$O(k*n)$。而两个变量的数量级均在$10^5$，所以总体运算次数在$10^{10}$数量级，完美超时。
正确思路：最小堆
既然数据的数量级在$10^5$，那么至少需要将其优化到$O(n \log (n))$的复杂度才能通过。
什么算法既能快速查找最小值，还能保持低复杂度呢？答案是最小堆。
自己本科竟然没有学过堆，今天做题的时候现学的。
参考csdn博客：https://blog.csdn.net/xiaomucgwlmx/article/details/103522410
- 分类讨论，对于“
costs所有项目都能遍历到的情况”，也就是说算法在寻找最小值时，总会在最后一轮的时候遍历了全部元素，这种情况下算法的目标就变成了取costs列表前k个最小元素，直接快排取最小，解决战斗；
什么时候会出现这种情况呢？可以从candidate=1的情况往外推找规律，k=2，len(costs)=4时，算法刚好从两边向中间遍历到了所有元素而没有剩余。也就是说len - 2 * candidate < k。 - 初始化两个堆：分别对应数组的前 candidates 个元素和后 candidates 个元素。这两个堆用来快速找出当前可选的最低成本工人。
然后通过双指针移动，遍历中间区域即将考虑的元素：i指向第一个堆后的第一个元素，即中间区域的开始。j指向最后一个堆前的最后一个元素，即中间区域的结束。 - 选择工人：
你通过比较两个堆的顶部元素来决定从哪个堆中取元素。
使用 heapreplace，这个函数弹出堆顶的最小元素，并将新元素添加到堆中，然后再次调整为最小堆。
根据堆的选择，移动相应的指针（i 或 j）以保证新元素能被加入到正确的堆中。
修改后的代码：
class Solution:
def totalCost(self, costs: List[int], k: int, candidates: int) -> int:
list_len = len(costs)
if( list_len - 2 * candidates < k ):
costs.sort()
return sum(costs[:k])
ans = 0
front_heap = costs[:candidates]
behind_heap = costs[-candidates:]
heapify(front_heap)
heapify(behind_heap)
# 声明2个指针，遍历中间没有被选到的元素
i = candidates
j = list_len - candidates -1
for _ in range(k):
if front_heap[0] <= behind_heap[0]:
ans += heapreplace(front_heap, costs[i])
i += 1
else:
ans += heapreplace(behind_heap, costs[j])
j -= 1
return ans总结复盘
- 审查变量的数量级，预估方法的时间复杂度。简单题可以暴力，到了中等难度就不行了。
python关于删除列表元素的方法：
List.remove()方法，删除对应值的第一个元素，如果没有找到对应的元素会报错。List.pop()方法，删除对应下标的元素，如果没有找到对应的元素会报错。
python的列表切片赋值操作会创建列表的新副本，而不是对原列表的引用。比如：
front = costs[:candidates]这个操作的front的地址和costs是不相同的。
python的堆操作
导入heapq库
heapify操作：原地修改，将给出的列表按照最小堆的排列顺序（就是按照最小堆的完全二叉树进行层次遍历）重排列表，没有返回值。
常用的函数：heapify(heap)：
作用：将列表 heap 转换为最小堆。heappush(heap, item)：
作用：将 item 添加到已有的堆 heap 中，并保持堆的特性。heappop(heap)：
作用：弹出并返回 heap 中的最小元素，保持剩余元素仍符合最小堆特性。heapreplace(heap, item)：
*作用：弹出堆中的最小元素，并将 item 加入堆中，是一步操作中完成的。这比单独先 heappop 然后 heappush 更高效，因为它只需要重新平衡一次堆。heappushpop(heap, item)：
作用：先将 item 压入堆中，然后弹出并返回 heap 中的最小元素。这个操作与 heapreplace 相似，但顺序相反。
Comments | NOTHING