1，问题描述
力扣第440周赛-第二题
3478. 选出和最大的 K 个元素
难度：中等
给你两个整数数组，nums1 和 nums2，长度均为 n，以及一个正整数 k 。
对从 0 到 n - 1 每个下标 i ，执行下述操作：
- 找出所有满足
nums1[j] 小于 nums1[i] 的下标 j 。
- 从这些下标对应的
nums2[j] 中选出 至多 k 个，并 最大化 这些值的总和作为结果。
返回一个长度为 n 的数组 answer ，其中 answer[i] 表示对应下标 i 的结果。
示例 1：
**输入：**nums1 = [4,2,1,5,3], nums2 = [10,20,30,40,50], k = 2
输出：[80,30,0,80,50]
解释：
- 对于
i = 0 ：满足 nums1[j] < nums1[0] 的下标为 [1, 2, 4] ，选出其中值最大的两个，结果为 50 + 30 = 80 。
- 对于
i = 1 ：满足 nums1[j] < nums1[1] 的下标为 [2] ，只能选择这个值，结果为 30 。
- 对于
i = 2 ：不存在满足 nums1[j] < nums1[2] 的下标，结果为 0 。
- 对于
i = 3 ：满足 nums1[j] < nums1[3] 的下标为 [0, 1, 2, 4] ，选出其中值最大的两个，结果为 50 + 30 = 80 。
- 对于
i = 4 ：满足 nums1[j] < nums1[4] 的下标为 [1, 2] ，选出其中值最大的两个，结果为 30 + 20 = 50 。
示例 2：
**输入：**nums1 = [2,2,2,2], nums2 = [3,1,2,3], k = 1
输出：[0,0,0,0]
**解释：**由于 nums1 中的所有元素相等，不存在满足条件 nums1[j] < nums1[i]，所有位置的结果都是 0 。
提示：
n == nums1.length == nums2.length1 <= n <= 1051 <= nums1[i], nums2[i] <= 1061 <= k <= n
2，初步思考
阅览题目的限制情况，发现数据量比较大，所以大概率有时间复杂度要求
拆解题目的问题，可以划分为2个问题：
1️⃣找出所有满足 nums1[j] 小于 nums1[i] 的下标 j
直接一个优先队列排个序，优先队列中是一个Pair，key为val、value为index坐标
2️⃣在已知的背景知识下，去取出前k个大的nums2中的下标为j的数据
像这种取出最大的k个数的直接使用最大堆、最小堆的方式来处理即可！（固定套路、问题模式识别）
使用上述的方式优化完，基本就没有问题了
3，代码处理
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
| import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
public class _3478选出和最大的K个元素 {
public long[] findMaxSum(int[] nums1, int[] nums2, int k) {
long[] res = new long[nums1.length];
List<Pair> pairs = coverToPriortyList(nums1);
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.comparingInt(p -> -p));
PriorityQueue<Integer> minHeap = new PriorityQueue<>(Comparator.comparingInt(p -> p));
res[pairs.getFirst().index] = 0;
minHeap.offer(nums2[pairs.getFirst().index]);
long sum = nums2[pairs.getFirst().index];
for (int i = 1; i < pairs.size(); i++) {
if (pairs.get(i).val == pairs.get(i - 1).val) {
res[pairs.get(i).index] = res[pairs.get(i - 1).index];
}else {
res[pairs.get(i).index] = sum;
}
if(i < k){
sum += nums2[pairs.get(i).index];
minHeap.offer(nums2[pairs.get(i).index]);
}else {
if(nums2[pairs.get(i).index] > minHeap.peek()){
sum += nums2[pairs.get(i).index] - minHeap.poll();
minHeap.offer(nums2[pairs.get(i).index]);
}
}
}
return res;
}
private List<Pair> coverToPriortyList(int[] nums1) {
PriorityQueue<Pair> heap = new PriorityQueue<>(Comparator.comparingInt(p -> p.val));
for (int i = 0; i < nums1.length; i++) {
heap.offer(new Pair(nums1[i], i));
}
List<Pair> list = new ArrayList<>();
for (int i = 0; i < nums1.length; i++) {
list.add(heap.poll());
}
return list;
}
static class Pair {
int val;
int index;
public Pair(int val, int index) {
this.val = val;
this.index = index;
}
}
public static void main(String[] args) {
_3478选出和最大的K个元素 test = new _3478选出和最大的K个元素();
int[] nums1 = new int[]{4, 2, 1, 5, 3};
int[] nums2 = new int[]{10, 20, 30, 40, 50};
test.findMaxSum(nums1, nums2, 2);
}
}
|
参考链接：
https://www.bilibili.com/video/BV15gRaYZE5o/?t=44m20s&vd_source=071ecfeeef39b447b8df51119337453a