寻找■最高的款项从多个整数名单 [英] Finding K Highest Sums from multiple integer lists

问题描述

由于多个列表/ ..need找出挑选每个list.Each列表中只有一个元素在K最高金额/数组包含在非递增序列整数整数数组。

Given several lists/array of integers ..need to find out the K highest sums picking only one element from each list.Each list/array contains integers in a non-increasing sequence.

例如，给定了输入：

[5,4,3,2,1]
[4,1]
[5,0,0]
[6,4,2]
[1] 

和如果K值是5即5最高款项。

and if the value of K is 5 i.e 5 highest sums.

其结果将是：

[21,20,19,19,18]

例如输入法可能看起来是这样的：

example of the input method might look something like this :

List<Integer> fetchHighestSums(int[][] lists,int n){  }

有人可以请帮助用java code的上方。

Can somebody please help with java code for the above.

推荐答案

这有一个简单的贪心算法。排序的所有号码到一个数组说，磷，标记每个号码与数组的任何信息。属于。 最初的总和将是所有的最高的（第一个），每个序列号的总和，并让每个编号S的存储在另一个数组S.我们去除P.这些数字下一步将替换这些号码中的一个小号具有下一最高数从P。我们选择从P中的下一个最高和删除相应的没有。从S和删除选定的没有。从P.我们这样做，直到我们得到k个最高编号S或至P是空的。 例如，如果

This has a simple greedy algorithm. Sort all the numbers into an array say P, labelling each number with information of the array the no. belongs to. Initially the sum would be the sum of all the highest(first) number from each array and lets store each of these no.s in another array S. We remove these numbers from P. Next step would be to replace one of these numbers from S with the next highest number from P. We pick the next highest from P and remove the corresponding no. from S and remove the selected no. from P. We do this till we get the k highest no.s or till P is empty. For example, if

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]

...等

这篇关于寻找■最高的款项从多个整数名单的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！