Medium

题目描述

给你一个下标从 0 开始、大小为 n 且由 正整数 组成的数组 nums 。

同时给你一个大小为 m 的二维数组 queries ，其中 queries[i] = [indexi, ki] 。

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

你需要依次对数组执行 m 次查询，其中第 i 次查询中你需要：

  • 如果下标 indexi 对应的元素还没有被标记，那么标记这个元素。
  • 然后标记 ki 个数组中还没有标记的 最小元素 。如果有多个这样的元素，优先标记下标 较小 的。如果少于 ki 个未标记元素，则标记所有剩下的未标记元素。

请你返回一个长度为 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] 。未标记元素的和为 1 + 2 + 3 = 6 。
  • 标记下标 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 <= 105
  • 1 <= nums[i] <= 105
  • queries[i].length == 2
  • 0 <= indexi, ki <= n - 1

解题思路

这道题的核心思路是维护数组的标记状态，并能快速找到最小的未标记元素。

算法思路：

  1. 预处理排序：创建一个索引数组，按照元素值进行排序，相同值时按索引排序。这样可以快速找到最小的未标记元素。

  2. 维护标记状态：使用布尔数组记录每个位置是否已被标记。

  3. 处理每个查询：

    • 首先标记指定索引的元素（如果未标记）
    • 然后从排序后的索引数组中顺序查找，标记k个最小的未标记元素
    • 计算剩余未标记元素的和

  4. 优化求和：维护总和变量，每次标记元素时减去对应值，避免重复计算。

关键优化点：

  • 使用排序后的索引数组，可以O(1)时间找到下一个最小未标记元素
  • 维护当前搜索位置指针，避免重复扫描已标记的元素
  • 预计算总和，通过减法得到未标记元素和

时间复杂度主要在排序步骤O(n log n)，查询处理为O(m + n)。

代码实现

class Solution {
public:
    vector<long long> unmarkedSumArray(vector<int>& nums, vector<vector<int>>& queries) {
        int n = nums.size();
        vector<int> indices(n);
        for (int i = 0; i < n; i++) {
            indices[i] = i;
        }
        
        // 按值排序，相同值按索引排序
        sort(indices.begin(), indices.end(), [&](int i, int j) {
            if (nums[i] != nums[j]) return nums[i] < nums[j];
            return i < j;
        });
        
        vector<bool> marked(n, false);
        long long totalSum = 0;
        for (int x : nums) totalSum += x;
        
        vector<long long> result;
        int ptr = 0; // 指向下一个可能标记的元素
        
        for (auto& query : queries) {
            int index = query[0], k = query[1];
            
            // 标记指定索引
            if (!marked[index]) {
                marked[index] = true;
                totalSum -= nums[index];
            }
            
            // 标记k个最小的未标记元素
            int count = 0;
            while (count < k && ptr < n) {
                int idx = indices[ptr];
                if (!marked[idx]) {
                    marked[idx] = true;
                    totalSum -= nums[idx];
                    count++;
                }
                ptr++;
            }
            
            result.push_back(totalSum);
        }
        
        return result;
    }
};

class Solution:
    def unmarkedSumArray(self, nums: List[int], queries: List[List[int]]) -> List[int]:
        n = len(nums)
        # 创建索引数组并排序
        indices = list(range(n))
        indices.sort(key=lambda i: (nums[i], i))
        
        marked = [False] * n
        total_sum = sum(nums)
        result = []
        ptr = 0  # 指向下一个可能标记的元素
        
        for index, k in queries:
            # 标记指定索引
            if not marked[index]:
                marked[index] = True
                total_sum -= nums[index]
            
            # 标记k个最小的未标记元素
            count = 0
            while count < k and ptr < n:
                idx = indices[ptr]
                if not marked[idx]:
                    marked[idx] = True
                    total_sum -= nums[idx]
                    count += 1
                ptr += 1
            
            result.append(total_sum)
        
        return result

public class Solution {
    public long[] UnmarkedSumArray(int[] nums, int[][] queries) {
        int n = nums.Length;
        var indices = new int[n];
        for (int i = 0; i < n; i++) {
            indices[i] = i;
        }
        
        Array.Sort(indices, (i, j) => {
            if (nums[i] != nums[j]) return nums[i].CompareTo(nums[j]);
            return i.CompareTo(j);
        });
        
        bool[] marked = new bool[n];
        long totalSum = 0;
        foreach (int x in nums) totalSum += x;
        
        long[] result = new long[queries.Length];
        int ptr = 0;
        
        for (int q = 0; q < queries.Length; q++) {
            int index = queries[q][0], k = queries[q][1];
            
            if (!marked[index]) {
                marked[index] = true;
                totalSum -= nums[index];
            }
            
            int count = 0;
            while (count < k && ptr < n) {
                int idx = indices[ptr];
                if (!marked[idx]) {
                    marked[idx] = true;
                    totalSum -= nums[idx];
                    count++;
                }
                ptr++;
            }
            
            result[q] = totalSum;
        }
        
        return result;
    }
}

var unmarkedSumArray = function(nums, queries) {
    const n = nums.length;
    const indices = Array.from({length: n}, (_, i) => i);
    
    indices.sort((i, j) => {
        if (nums[i] !== nums[j]) return nums[i] - nums[j];
        return i - j;
    });
    
    const marked = new Array(n).fill(false);
    let totalSum = nums.reduce((sum, x) => sum + x, 0);
    const result = [];
    let ptr = 0;
    
    for (const [index, k] of queries) {
        if (!marked[index]) {
            marked[index] = true;
            totalSum -= nums[index];
        }
        
        let count = 0;
        while (count < k && ptr < n) {
            const idx = indices[ptr];
            if (!marked[idx]) {
                marked[idx] = true;
                totalSum -= nums[idx];
                count++;
            }
            ptr++;
        }
        
        result.push(totalSum);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型时间复杂度空间复杂度
时间复杂度O(n log n + m + n)O(n)
空间复杂度O(n)O(n)

说明：

  • 时间复杂度：O(n log n)用于排序索引数组，O(m + n)用于处理所有查询（每个元素最多被访问一次）
  • 空间复杂度：O(n)用于存储索引数组、标记数组等辅助空间