执行操作标记数组中的元素
难度:
标签:
题目描述
You are given a 0-indexed array nums of size n consisting of positive integers.
You are also given a 2D array queries of size m where queries[i] = [indexi, ki].
Initially all elements of the array are unmarked.
You need to apply m queries on the array in order, where on the ith query you do the following:
- Mark the element at index
indexiif it is not already marked. - Then mark
kiunmarked elements in the array with the smallest values. If multiple such elements exist, mark the ones with the smallest indices. And if less thankiunmarked elements exist, then mark all of them.
Return an array answer of size m where answer[i] is the sum of unmarked elements in the array after the ith query.
Example 1:
Input: nums = [1,2,2,1,2,3,1], queries = [[1,2],[3,3],[4,2]]
Output: [8,3,0]
Explanation:
We do the following queries on the array:
- Mark the element at index
1, and2of the smallest unmarked elements with the smallest indices if they exist, the marked elements now arenums = [1,2,2,1,2,3,1]. The sum of unmarked elements is2 + 2 + 3 + 1 = 8. - Mark the element at index
3, since it is already marked we skip it. Then we mark3of the smallest unmarked elements with the smallest indices, the marked elements now arenums = [1,2,2,1,2,3,1]. The sum of unmarked elements is3. - Mark the element at index
4, since it is already marked we skip it. Then we mark2of the smallest unmarked elements with the smallest indices if they exist, the marked elements now arenums = [1,2,2,1,2,3,1]. The sum of unmarked elements is0.
Example 2:
Input: nums = [1,4,2,3], queries = [[0,1]]
Output: [7]
Explanation: We do one query which is mark the element at index 0 and mark the smallest element among unmarked elements. The marked elements will be nums = [1,4,2,3], and the sum of unmarked elements is 4 + 3 = 7.
Constraints:
n == nums.lengthm == queries.length1 <= m <= n <= 1051 <= nums[i] <= 105queries[i].length == 20 <= indexi, ki <= n - 1
代码结果
运行时间: 257 ms, 内存: 38.0 MB
/*
* 思路：
* 1. 使用Java Stream API进行集合操作和筛选。
* 2. 每次操作后标记相应元素并计算未标记元素的和。
*/
import java.util.*;
import java.util.stream.*;
public class SolutionStream {
public int[] minOperations(int[] nums, int[][] queries) {
int n = nums.length;
int m = queries.length;
boolean[] marked = new boolean[n];
int[] answer = new int[m];
int unmarkedSum = Arrays.stream(nums).sum();
for (int i = 0; i < m; i++) {
int index = queries[i][0];
int k = queries[i][1];
if (!marked[index]) {
marked[index] = true;
unmarkedSum -= nums[index];
}
// 找到最小的k个未标记元素并标记
List<Integer> unmarkedElements = IntStream.range(0, n)
.filter(j -> !marked[j])
.mapToObj(j -> nums[j])
.sorted()
.limit(k)
.collect(Collectors.toList());
for (int val : unmarkedElements) {
for (int j = 0; j < n; j++) {
if (!marked[j] && nums[j] == val) {
marked[j] = true;
unmarkedSum -= nums[j];
break;
}
}
}
answer[i] = unmarkedSum;
}
return answer;
}
}解释
方法:
时间复杂度:
空间复杂度: