给定A、B两个数列，各包含n个数，分别从A和B中任意取一个数相加得到和，这样会有n^2种结果(包括重复的)，求n^2个结果中前n个最小的和。java实现

可以使用一个最小堆来维护前n个最小的和。
首先将A和B排序，然后从A和B中各取一个数相加得到和，将和以及两个数的下标（用于避免重复）放入最小堆中。然后从最小堆中取出堆顶元素，即当前最小的和，将其加入结果数组中。然后将堆顶元素对应的两个数在各自的数列中向后移动一位，再将新得到的和以及两个数的下标放入最小堆中。重复这个过程n次，即可得到前n个最小的和。
以下是Java实现：
import java.util.*;

public class MinSum {
public static void main(String[] args) {
int[] A = {1, 3, 5, 7};
int[] B = {2, 4, 6, 8};
int n = 4;

PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
for (int i = 0; i < n; i++) {
pq.offer(new int[] {A[i] + B[0], i, 0});
}

int[] res = new int[n];
for (int i = 0; i < n; i++) {
int[] cur = pq.poll();
res[i] = cur[0];
int aIdx = cur[1], bIdx = cur[2];
if (bIdx < n - 1) {
pq.offer(new int[] {A[aIdx] + B[bIdx + 1], aIdx, bIdx + 1});
}
}

System.out.println(Arrays.toString(res)); // [3, 4, 5, 6]
}
}
登录后复制