class Solution {
public:
vector<long long> unmarkedSumArray(vector<int>& nums, vector<vector<int>>& queries) {
}
};
3080. 执行操作标记数组中的元素
给你一个长度为 n 下标从 0 开始的正整数数组 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] 。未标记元素的和为 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.lengthm == queries.length1 <= m <= n <= 1051 <= n <= 105queries[i].length == 20 <= indexi, ki <= n - 1原站题解
golang 解法, 执行用时: 210 ms, 内存消耗: 12.7 MB, 提交时间: 2024-03-18 22:34:15
func unmarkedSumArray(nums []int, queries [][]int) []int64 {
s, n := 0, len(nums)
ids := make([]int, n)
for i, x := range nums {
s += x
ids[i] = i
}
slices.SortStableFunc(ids, func(i, j int) int { return nums[i] - nums[j] })
ans := make([]int64, len(queries))
j := 0
for qi, p := range queries {
i, k := p[0], p[1]
s -= nums[i]
nums[i] = 0 // 标记
for ; j < n && k > 0; j++ {
i := ids[j]
if nums[i] > 0 { // 没有被标记
s -= nums[i]
nums[i] = 0
k--
}
}
ans[qi] = int64(s)
}
return ans
}
cpp 解法, 执行用时: 257 ms, 内存消耗: 121.5 MB, 提交时间: 2024-03-18 22:33:39
class Solution {
public:
vector<long long> unmarkedSumArray(vector<int> &nums, vector<vector<int>> &queries) {
int n = nums.size();
long long s = accumulate(nums.begin(), nums.end(), 0LL);
vector<int> ids(n);
iota(ids.begin(), ids.end(), 0);
ranges::stable_sort(ids, [&](int i, int j) { return nums[i] < nums[j]; });
vector<long long> ans;
int j = 0;
for (auto &q : queries) {
int i = q[0], k = q[1];
s -= nums[i];
nums[i] = 0; // 标记
for (; j < n && k; j++) {
i = ids[j];
if (nums[i] > 0) { // 没有被标记
s -= nums[i];
nums[i] = 0;
k--;
}
}
ans.push_back(s);
}
return ans;
}
};
java 解法, 执行用时: 78 ms, 内存消耗: 69.8 MB, 提交时间: 2024-03-18 22:33:19
class Solution {
public long[] unmarkedSumArray(int[] nums, int[][] queries) {
int n = nums.length;
long s = 0;
Integer[] ids = new Integer[n];
for (int i = 0; i < n; i++) {
s += nums[i];
ids[i] = i;
}
Arrays.sort(ids, (i, j) -> nums[i] - nums[j]); // 稳定排序
long[] ans = new long[queries.length];
int j = 0;
for (int qi = 0; qi < queries.length; qi++) {
int[] q = queries[qi];
int i = q[0];
int k = q[1];
s -= nums[i];
nums[i] = 0; // 标记
for (; j < n && k > 0; j++) {
i = ids[j];
if (nums[i] > 0) { // 没有被标记
s -= nums[i];
nums[i] = 0;
k--;
}
}
ans[qi] = s;
}
return ans;
}
}
python3 解法, 执行用时: 253 ms, 内存消耗: 38.8 MB, 提交时间: 2024-03-18 22:33:00
class Solution:
def unmarkedSumArray(self, nums: List[int], queries: List[List[int]]) -> List[int]:
n = len(nums)
s = sum(nums)
ids = sorted(range(n), key=lambda i: nums[i]) # 稳定排序
ans = []
j = 0
for i, k in queries:
s -= nums[i]
nums[i] = 0 # 标记
while j < n and k:
i = ids[j]
if nums[i]: # 没有被标记
s -= nums[i]
nums[i] = 0
k -= 1
j += 1
ans.append(s)
return ans