两有序数组间相加的TOPK问题
给定两有序数组arr1和arr2，以及整数k，返回来自arr1和arr2两个数相加和最大的前k个，此外两数必须来自不同的数组。
示例：
arr1 = [1 2 3 4 5]
arr2 = [3 5 7 9 11]
k = 4
输出
[16 15 14 14]
要求时间复杂度为O(klog(k))解决方案：
我们发现最大的元素为arr1[M - 1] 与 arr2[N - 1]之和，比起稍小的两组数据分别为arr1[M - 1] + arr2[N - 2]和arr1[M - 2] + arr2[N - 1]。
定义一大根堆，初始将arr1[M - 1] + arr2[N - 1]存入堆中。
然后使用bfs，每次从堆中弹出最大值元素记做（i, j），并将其的(i - 1, j) 和 (i , j - 1)入堆。如此弹出k个元素即可。
public class Main{
public static class Node{
int x;
int y;
public Node(int x, int y) {
this.x = x;
this.y = y;
}
}
public static int[][] directs = {{0, -1}, {-1, 0}};
public static List<Integer>selution(int[] arr1, int[] arr2, int k) {
Queue<Node> maxHeap = new PriorityQueue<>(new Comparator<Node>() {
public int compare(Node node1, Node node2) {
return (arr1[node2.x] + arr2[node2.y]) - (arr1[node1.x] + arr2[node1.y]);
}
});
List<Integer> ans = new ArrayList<>(k);
int M = arr1.length;
int N = arr2.length;
boolean[][] visted = new boolean[M][N];
maxHeap.add(new Node(M - 1, N - 1));
visted[M - 1][N - 1] = true;
for(int i = 0; i < k; i++) {
Node cur = maxHeap.remove();
ans.add(arr1[cur.x] + arr2[cur.y]);
for(int[] direct : directs) {
int x = cur.x + direct[0];
int y = cur.y + direct[1];
if(x < 0 || y < 0 || visted[x][y]) {
continue;
}
maxHeap.add(new Node(x, y));
}
}
return ans;
}
}document.querySelectorAll('.github-emoji') .forEach(el => { if (!el.dataset.src) { return; } const img = document.createElement('img'); img.style = 'display:none !important;'; img.src = el.dataset.src; img.addEventListener('error', () => { img.remove(); el.style.color = 'inherit'; el.style.backgroundImage = 'none'; el.style.background = 'none'; }); img.addEventListener('load', () => { img.remove(); }); document.body.appendChild(img); });
腾讯云开发者
