Input: nums1 =[4,2,1,5,3], nums2 =[10,20,30,40,50], k =2Output: [80,30,0,80,50]Explanation:
* For `i = 0`: Select the 2 largest values from `nums2` at indices `[1, 2, 4]` where `nums1[j] < nums1[0]`, resulting in`50 + 30 = 80`.* For `i = 1`: Select the 2 largest values from `nums2` at index `[2]` where `nums1[j] < nums1[1]`, resulting in30.* For `i = 2`: No indices satisfy `nums1[j] < nums1[2]`, resulting in0.* For `i = 3`: Select the 2 largest values from `nums2` at indices `[0, 1, 2, 4]` where `nums1[j] < nums1[3]`, resulting in`50 + 30 = 80`.* For `i = 4`: Select the 2 largest values from `nums2` at indices `[1, 2]` where `nums1[j] < nums1[4]`, resulting in`30 + 20 = 50`.
Input: nums1 =[2,2,2,2], nums2 =[3,1,2,3], k =1Output: [0,0,0,0]Explanation:
Since all elements in`nums1` are equal, no indices satisfy the condition `nums1[j] < nums1[i]`for any `i`, resulting in0for all positions.
For each index i, we want to find all indices j where nums1[j] < nums1[i] and select the k largest nums2[j] values. This is a classic use case for sorting and a max-heap (priority queue).
By sorting the indices by nums1 value, we can process all indices in increasing order. For each i, all previous indices have nums1[j] < nums1[i]. We can maintain a max-heap of nums2[j] values for all such j and efficiently get the sum of the k largest values for each i.
classSolution {
public: vector<int> maxSum(vector<int>& nums1, vector<int>& nums2, int k) {
int n = nums1.size();
vector<int> idx(n);
iota(idx.begin(), idx.end(), 0);
sort(idx.begin(), idx.end(), [&](int a, int b) { return nums1[a] < nums1[b]; });
vector<int> ans(n);
multiset<int> heap;
for (int i =0; i < n; ++i) {
int cur = idx[i];
vector<int> topk;
auto it = heap.rbegin();
for (int cnt =0; cnt < k && it != heap.rend(); ++cnt, ++it) topk.push_back(*it);
ans[cur] = accumulate(topk.begin(), topk.end(), 0);
heap.insert(nums2[cur]);
}
return ans;
}
};
classSolution {
funmaxSum(nums1: IntArray, nums2: IntArray, k: Int): IntArray {
val n = nums1.size
val idx = nums1.indices.sortedBy { nums1[it] }
val ans = IntArray(n)
val heap = mutableListOf<Int>()
for (i in0 until n) {
val cur = idx[i]
val topk = heap.sortedDescending().take(k)
ans[cur] = topk.sum()
heap.add(nums2[cur])
}
return ans
}
}