What is the main pattern used in Mark Elements on Array by Performing Queries?

The key pattern is array scanning combined with hash table lookup to track marked elements efficiently.

Can I avoid sorting to solve this problem?

Sorting is optional but helps quickly identify the ki smallest unmarked elements; skipping it may require more complex selection logic.

How do I track which elements are already marked?

Use a boolean array or hash table indexed by element positions to record which elements are marked to prevent double-counting.

What is the time complexity for processing all queries?

Sorting costs O(n log n) once, then each query uses O(ki) hash lookups; overall complexity depends on the sum of all ki across queries.

Why does naive repeated sum computation fail?

Recomputing the sum of unmarked elements from scratch after each query results in O(n * m) time, which exceeds limits for large arrays.

#3080

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

执行操作标记数组中的元素

给你一个长度为 n 下标从 0 开始的正整数数组 nums 。同时给你一个长度为 m 的二维操作数组 queries ，其中 queries[i] = [index i , k i ] 。一开始，数组中的所有元素都未标记。你需要依次对数组执行 m 次操作，第 i 次操作中，你需要执行：如…

数组哈希表排序堆（优先队列）模拟

题目描述

给你一个长度为 n 下标从 0 开始的正整数数组 nums 。

同时给你一个长度为 m 的二维操作数组 queries ，其中 queries[i] = [index_i, k_i] 。

一开始，数组中的所有元素都 未标记 。

你需要依次对数组执行 m 次操作，第 i 次操作中，你需要执行：

如果下标 index_i 对应的元素还没标记，那么标记这个元素。
然后标记 k_i 个数组中还没有标记的最小元素。如果有元素的值相等，那么优先标记它们中下标较小的。如果少于 k_i 个未标记元素存在，那么将它们全部标记。

请你返回一个长度为 m 的数组 answer ，其中 answer[i]是第 i 次操作后数组中还没标记元素的和。

示例 1：

输入：nums = [1,2,2,1,2,3,1], queries = [[1,2],[3,3],[4,2]]

输出：[8,3,0]

解释：

我们依次对数组做以下操作：

标记下标为 1 的元素，同时标记 2 个未标记的最小元素。标记完后数组为 nums = [1,2,2,1,2,3,1] 。未标记元素的和为 2 + 2 + 3 + 1 = 8 。
标记下标为 3 的元素，由于它已经被标记过了，所以我们忽略这次标记，同时标记最靠前的 3 个未标记的最小元素。标记完后数组为 nums = [1,2,2,1,2,3,1] 。未标记元素的和为 3 。
标记下标为 4 的元素，由于它已经被标记过了，所以我们忽略这次标记，同时标记最靠前的 2 个未标记的最小元素。标记完后数组为 nums = [1,2,2,1,2,3,1] 。未标记元素的和为 0 。

示例 2：

输入：nums = [1,4,2,3], queries = [[0,1]]

输出：[7]

解释：我们执行一次操作，将下标为 0 处的元素标记，并且标记最靠前的 1 个未标记的最小元素。标记完后数组为 nums = [1,4,2,3] 。未标记元素的和为 4 + 3 = 7 。

提示：

n == nums.length
m == queries.length
1 <= m <= n <= 10⁵
1 <= nums[i] <= 10⁵
queries[i].length == 2
0 <= index_i, k_i <= n - 1

lightbulb

解题思路

方法一：排序 + 模拟

我们先计算出数组 $nums$ 的总和 $s$ ，定义一个数组 $mark$ 用来标记数组中的元素是否被标记过，初始化所有元素都未被标记。

然后我们创建一个数组 $arr$ ，数组中的每个元素是一个二元组 $(x, i)$ ，表示数组中的第 $i$ 个元素的值为 $x$ 。我们对数组 $arr$ 按照元素的值进行排序，如果元素的值相等，我们按照下标从小到大的顺序进行排序。

接下来我们遍历数组 $queries$ ，对于每个查询 $[index, k]$ ，我们首先判断下标 $index$ 对应的元素是否被标记过，如果没有被标记过，我们将其标记，并且将 $s$ 减去下标 $index$ 对应的元素的值。然后我们遍历数组 $arr$ ，对于每个元素 $(x, i)$ ，如果元素 $i$ 没有被标记过，我们将其标记，并且将 $s$ 减去元素 $i$ 对应的值 $x$ ，直到 $k$ 为 $0$ 或者数组 $arr$ 遍历完。然后我们将 $s$ 加入答案数组中。

遍历完所有的查询后，我们就得到了答案数组。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是数组 $nums$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

class Solution:
    def unmarkedSumArray(self, nums: List[int], queries: List[List[int]]) -> List[int]:
        n = len(nums)
        s = sum(nums)
        mark = [False] * n
        arr = sorted((x, i) for i, x in enumerate(nums))
        j = 0
        ans = []
        for index, k in queries:
            if not mark[index]:
                mark[index] = True
                s -= nums[index]
            while k and j < n:
                if not mark[arr[j][1]]:
                    mark[arr[j][1]] = True
                    s -= arr[j][0]
                    k -= 1
                j += 1
            ans.append(s)
        return ans

speed

复杂度分析

指标	值
时间	complexity depends on sorting nums once (O(n log n)) and processing m queries with O(1) hash checks per element. Space complexity is O(n) for the hash table tracking marked elements.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
They may ask how you avoid double-counting marked elements across queries.
question_mark
They may hint at using additional data structures like hash tables to track marks.
question_mark
They may suggest considering sorting to quickly find the ki smallest unmarked elements.

warning

常见陷阱

外企场景

error
Recomputing the sum of unmarked elements from scratch after every query.
error
Marking elements without checking if they are already marked, causing errors.
error
Ignoring the optimal combination of array scanning and hash lookup, leading to TLE.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Instead of marking the smallest ki elements, mark the largest ki elements and compute sums.
arrow_right_alt
Allow queries that mark ranges instead of single indices, requiring interval tracking.
arrow_right_alt
Modify nums dynamically between queries, needing a flexible update strategy.

help

常见问题

外企场景

继续练习

#2593 标记所有元素后数组的分数 #2402 会议室 III #2357 使数组中所有元素都等于零