Leetcode 3080. Mark Elements on Array by Performing Queries
- Leetcode 3080. Mark Elements on Array by Performing Queries
- 1. 解题思路
- 2. 代码实现
- 题目链接：3080. Mark Elements on Array by Performing Queries
1. 解题思路
这一题我们只需要按照题意进行一下实现就行了。具体来说的话，我们只需要依序遍历一下query，然后在每个query过程中判断一下目标元素之前是否有被mark过，并额外找出最小的 k i k_i ki个元素进行mark即可。
因此，我们要做的就是如何最优地完成这两个操作，前者我们用一个hash table来记录下所有被mark的位置，后者我们用一个有序数列来对其进行维护即可。
2. 代码实现
给出python代码实现如下：
class Solution:
def unmarkedSumArray(self, nums: List[int], queries: List[List[int]]) -> List[int]:
marked = set()
q = sorted([(x, i) for i, x in enumerate(nums)])
s = sum(nums)
ans = []
for idx, k in queries:
if idx not in marked:
s -= nums[idx]
q.pop(bisect.bisect_left(q, (nums[idx], idx)))
marked.add(idx)
for x, i in q[:k]:
s -= x
marked.add(i)
q = q[k:]
ans.append(s)
return ans
提交代码评测得到：耗时1076ms，占用内存50.3MB。