给定多个整数列表/数组..需要从每个列表中仅选取一个元素找出 K 个最高和。每个列表/数组包含非递增序列中的整数。
例如,给定输入:
[5,4,3,2,1]
[4,1]
[5,0,0]
[6,4,2]
[1]
如果 K 的值为 5,即 5 个最高和。
结果将是:
[21,20,19,19,18]
输入法的示例可能如下所示:
List<Integer> fetchHighestSums(int[][] lists,int n){ }
有人可以帮忙编写上面的 java 代码吗?
这有一个简单的贪心算法。将所有数字排序到一个数组中,比如 P,用数组的信息标记每个数字。属于。
最初,总和将是每个数组中所有最高(第一个)数字的总和,让我们将这些数字中的每一个存储在另一个数组 S 中。我们从 P 中删除这些数字。下一步将替换这些数字中的一个S 与 P 中的下一个最大数字。我们从 P 中选择下一个最大的数字并删除相应的数字。从 S 中删除选定的编号。从 P 开始。我们这样做直到我们得到 k 个最高的 no.s 或直到 P 为空。
例如,如果
A = [5,4,3,2,1]
B = [4,1]
C = [5,0,0]
D = [6,4,2]
E = [1]
P = D[0] A[0] C[0] A[1] B[0] D[1] A[2] D[2] A[3] D[2] A[4] B[1] E[0] C[2]
S = D[0] + A[0] + C[0] + B[0] + E[0] and P = A[1] D[1] A[2] D[2] A[3] D[2] A[4] B[1] C[2]
S = D[0] + A[1] + C[0] + B[0] + E[0] and P = D[1] A[2] D[2] A[3] D[2] A[4] B[1] C[2]
S = D[1] + A[0] + C[0] + B[0] + E[0] and P = A[2] D[2] A[3] D[2] A[4] B[1] C[2]
S = D[0] + A[2] + C[0] + B[0] + E[0] and P = D[2] A[3] D[2] A[4] B[1] C[2]
...等等