您将获得两个已排序大小分别为n和m的数组。你的任务（如果你愿意接受的话）是输出形式为
可以在这里找到一个O(k log k)的解决方案。有传言称存在O(k)或O(n)的解决方案。是否存在这样的解决方案？
a[i]+b[j]的最大k个和。可以在这里找到一个O(k log k)的解决方案。有传言称存在O(k)或O(n)的解决方案。是否存在这样的解决方案？
找出两个已排序数组中前k大的数字和。
10
- ripper234
8
2你提供的链接中的问题是A[i] + B[j]的前n个最大值，其中A和B是长度为n的排序数组。但实际上，在这个问题中并不一定是这样。事实上，在那个帖子中，James Fingas（见第2页）已经给出了一个O(n)时间复杂度的算法（我相信对于k=n）。无论如何，还是点个赞。 - Aryabhatta
@Moron - 对不起，我把这个问题和另一个问题搞混了。我已经编辑过了。你确定James的解决方案是有效的吗？ - ripper234
1@ripper：我曾经在那个论坛上常驻几年，我很确定詹姆斯·芬加斯是那里更好/更理智的拼图解决者之一（他在我频繁访问之前就是常客）。当然，我从未努力去理解那个解决方案，但考虑到Hippo（我相信还有Grimbal）的同意，我对正确性感到相当自信。当然，这并不是证明。 - Aryabhatta
@ripper234，我其实不确定是否存在O(k)的解决方案。为了简单起见，假设m = n（数组大小）。我可以构造输入，使得从左下到右上的对角线具有相同的值。现在，我可以稍微改变这个输入，使得对角线上的任何一个元素都比其他元素大1（并且对角线上方和左侧的所有元素都严格更大）。现在当你到达对角线时，你该如何选择？ - rlibby
请阅读我在此帖子中的回答：https://dev59.com/eG445IYBdhLWcg3w9O7R#29352604 - Fei
显示剩余3条评论
4个回答
11
我发现你链接中的回答大多含糊不清且结构混乱。以下是一个时间复杂度为 O(k * log(min(m, n))) O(k * log(m + n)) O(k * log(k)) 的算法。
假设它们是按降序排列的。想象一下，您可以按以下方式计算出 m*n 矩阵的总和：
for i from 0 to m
for j from 0 to n
sums[i][j] = a[i] + b[j]
q : priority queue (decreasing) := empty priority queue
add (0, 0) to q with priority a[0] + b[0]
while k > 0:
k--
x := pop q
output x
(i, j) : tuple of int,int := position of x
if i < m:
add (i + 1, j) to q with priority a[i + 1] + b[j]
if j < n:
add (i, j + 1) to q with priority a[i] + b[j + 1]
分析：
- 循环执行 k 次。
- 每次迭代有一个 pop 操作。
- 每次迭代最多有两个 insert 操作。
- 优先队列的最大大小为
O(min(m, n))O(m + n)O(k)。 - 可以使用二叉堆实现优先队列，pop 和 insert 操作的时间复杂度为 log(size)。
- 因此，该算法的时间复杂度为
O(k * log(min(m, n)))O(k * log(m + n))O(k * log(k))。
请注意，一般的优先队列抽象数据类型需要进行修改才能忽略重复项。或者，您可以维护一个单独的集合结构，在添加到队列之前首先检查集合成员资格，并在从队列中弹出后从集合中删除。这两种方法都不会恶化时间或空间复杂度。
如果有兴趣，我可以用Java编写这个算法。
编辑：修正了复杂度。虽然存在我所描述的复杂度的算法，但它与这个算法略有不同。您需要小心避免添加某些节点。我的简单解决方案会过早地向队列中添加许多节点。
- rlibby
7
这是O(mn)（创建总和矩阵需要O(mn)），OP希望最多只需O(n + m + k)。 - Saeed Amiri
2@Saeed，谢谢，但我实际上并没有创建那个矩阵。我只是描述了我对问题的想象。如果您在我提供的分析中发现问题，请指出来。 - rlibby
@ripper234，如果我正确地设置了队列大小限制，那么你是正确的。但不幸的是，我认为它实际上是O(m + n)，而不是我写的O(min(m, n))。它可以被设置为O(min(m, n))，但需要稍微多做一些工作。 - rlibby
为什么队列大小的上限是(m+n)，我认为应该是(mn)？ - outlaw
1实际上，正确的时间复杂度是klogk。其中k是找到的元素数量。因此，需要维护一个大小为K的堆。将元素对角线地放入堆中，直到找到k个元素为止。无需遍历所有元素，因为data_left_side > data和data_up_side>data。 - Chris Su
显示剩余2条评论
1
private static class FrontierElem implements Comparable<FrontierElem> {
int value;
int aIdx;
int bIdx;
public FrontierElem(int value, int aIdx, int bIdx) {
this.value = value;
this.aIdx = aIdx;
this.bIdx = bIdx;
}
@Override
public int compareTo(FrontierElem o) {
return o.value - value;
}
}
public static void findMaxSum( int [] a, int [] b, int k ) {
Integer [] frontierA = new Integer[ a.length ];
Integer [] frontierB = new Integer[ b.length ];
PriorityQueue<FrontierElem> q = new PriorityQueue<MaxSum.FrontierElem>();
frontierA[0] = frontierB[0]=0;
q.add( new FrontierElem( a[0]+b[0], 0, 0));
while( k > 0 ) {
FrontierElem f = q.poll();
System.out.println( f.value+" "+q.size() );
k--;
frontierA[ f.aIdx ] = frontierB[ f.bIdx ] = null;
int fRight = f.aIdx+1;
int fDown = f.bIdx+1;
if( fRight < a.length && frontierA[ fRight ] == null ) {
q.add( new FrontierElem( a[fRight]+b[f.bIdx], fRight, f.bIdx));
frontierA[ fRight ] = f.bIdx;
frontierB[ f.bIdx ] = fRight;
}
if( fDown < b.length && frontierB[ fDown ] == null ) {
q.add( new FrontierElem( a[f.aIdx]+b[fDown], f.aIdx, fDown));
frontierA[ f.aIdx ] = fDown;
frontierB[ fDown ] = f.aIdx;
}
}
}
这个想法与其他解决方案类似，但观察到当你从矩阵中添加到结果集时，每一步我们集合中的下一个元素只能来自当前集合是凹的位置。我称这些元素为前沿元素，并在两个数组中跟踪它们的位置和优先级队列中的值。这有助于保持队列大小，但我还没有完全弄清楚它可以减少多少。看起来大约是
sqrt(k)，但我不太确定。（当然，frontierA/B数组可以是简单的布尔数组，但这样它们完全定义了我的结果集，在此示例中未使用，但在其他情况下可能会有用。）
- biziclop
3
很抱歉我暂时没有时间仔细阅读，但你应该可以通过跟踪边界的一个数组来完成它。选择长度最小的那个。这样可以将算法的时间复杂度降至O(min(m, n) max size for the array)，而且运行时间为O(k * log(min(k, m, n)))。我会在一天内再次查看。 - rlibby
@rlibby 我猜你可以这样做，但是这种方式无论你感兴趣的是哪个轴，前沿查找都只需要O(1)时间。 - biziclop
凸性洞察非常好，但我不知道它如何提高最坏情况下的空间复杂度。当矩阵的覆盖部分采用1大小的步骤形式时，候选集合是O(n+m)，对吧？ - Eyal Schneider
0
由于前提条件是该数组已排序，因此让我们考虑以下情况：当N=5时；
A [] = {1,2,3,4,5}
B [] = {496,497,498,499,500}
现在，由于我们知道A和B中N-1的总和最高，因此只需将其插入堆中，并加上A和B元素的索引（为什么要使用索引？我们马上就会知道）。
H.insert(A[N-1]+B[N-1],N-1,N-1);
现在
while(!H.empty()) { // the time heap is not empty
H.pop(); // this will give you the sum you are looking for
The indexes which we got at the time of pop, we shall use them for selecting the next sum element.
Consider the following :
if we have i & j as the indexes in A & B , then the next element would be max ( A[i]+B[j-1], A[i-1]+B[j], A[i+1]+B[j+1] ) ,
So, insert the same if that has not been inserted in the heap
hence
(i,j)= max ( A[i]+B[j-1], A[i-1]+B[j], A[i+1]+B[j+1] ) ;
if(Hash[i,j]){ // not inserted
H.insert (i,j);
}else{
get the next max from max ( A[i]+B[j-1], A[i-1]+B[j], A[i+1]+B[j+1] ) ; and insert.
}
K pop-ing them will give you max elements required.
希望对你有所帮助
- AnotherDeveloper
0
非常感谢@rlibby和@xuhdev提出了这样一个原创性的解决问题的想法。我曾经参加过一次类似的编码练习面试，需要在K个降序排序的数组中找到由K个元素组成的N个最大和 - 这意味着我们必须从每个排序数组中选择1个元素来构建最大的总和。
以下是我的代码，请仔细查看那些代码块注释 :D
Example: List findHighestSums(int[][] lists, int n) {}
[5,4,3,2,1]
[4,1]
[5,0,0]
[6,4,2]
[1]
and a value of 5 for n, your procedure should return a List of size 5:
[21,20,19,19,18]
以下是我的代码，请仔细查看那些代码块注释 :D
private class Pair implements Comparable<Pair>{
String state;
int sum;
public Pair(String state, int sum) {
this.state = state;
this.sum = sum;
}
@Override
public int compareTo(Pair o) {
// Max heap
return o.sum - this.sum;
}
}
List<Integer> findHighestSums(int[][] lists, int n) {
int numOfLists = lists.length;
int totalCharacterInState = 0;
/*
* To represent State of combination of largest sum as String
* The number of characters for each list should be Math.ceil(log(list[i].length))
* For example:
* If list1 length contains from 11 to 100 elements
* Then the State represents for list1 will require 2 characters
*/
int[] positionStartingCharacterOfListState = new int[numOfLists + 1];
positionStartingCharacterOfListState[0] = 0;
// the reason to set less or equal here is to get the position starting character of the last list
for(int i = 1; i <= numOfLists; i++) {
int previousListNumOfCharacters = 1;
if(lists[i-1].length > 10) {
previousListNumOfCharacters = (int)Math.ceil(Math.log10(lists[i-1].length));
}
positionStartingCharacterOfListState[i] = positionStartingCharacterOfListState[i-1] + previousListNumOfCharacters;
totalCharacterInState += previousListNumOfCharacters;
}
// Check the state <---> make sure that combination of a sum is new
Set<String> states = new HashSet<>();
List<Integer> result = new ArrayList<>();
StringBuilder sb = new StringBuilder();
// This is a max heap contain <State, largestSum>
PriorityQueue<Pair> pq = new PriorityQueue<>();
char[] stateChars = new char[totalCharacterInState];
Arrays.fill(stateChars, '0');
sb.append(stateChars);
String firstState = sb.toString();
states.add(firstState);
int firstLargestSum = 0;
for(int i = 0; i < numOfLists; i++) firstLargestSum += lists[i][0];
// Imagine this is the initial state in a graph
pq.add(new Pair(firstState, firstLargestSum));
while(n > 0) {
// In case n is larger than the number of combinations of all list entries
if(pq.isEmpty()) break;
Pair top = pq.poll();
String currentState = top.state;
int currentSum = top.sum;
/*
* Loop for all lists and generate new states of which only 1 character is different from the former state
* For example: the initial state (Stage 0) 0 0 0 0 0
* So the next states (Stage 1) should be:
* 1 0 0 0 0
* 0 1 0 0 0 (choose element at index 2 from 2nd array)
* 0 0 1 0 0 (choose element at index 2 from 3rd array)
* 0 0 0 0 1
* But don't forget to check whether index in any lists have exceeded list's length
*/
for(int i = 0; i < numOfLists; i++) {
int indexInList = Integer.parseInt(
currentState.substring(positionStartingCharacterOfListState[i], positionStartingCharacterOfListState[i+1]));
if( indexInList < lists[i].length - 1) {
int numberOfCharacters = positionStartingCharacterOfListState[i+1] - positionStartingCharacterOfListState[i];
sb = new StringBuilder(currentState.substring(0, positionStartingCharacterOfListState[i]));
sb.append(String.format("%0" + numberOfCharacters + "d", indexInList + 1));
sb.append(currentState.substring(positionStartingCharacterOfListState[i+1]));
String newState = sb.toString();
if(!states.contains(newState)) {
// The newSum is always <= currentSum
int newSum = currentSum - lists[i][indexInList] + lists[i][indexInList+1];
states.add(newState);
// Using priority queue, we can immediately retrieve the largest Sum at Stage k and track all other unused states.
// From that Stage k largest Sum's state, then we can generate new states
// Those sums composed by recently generated states don't guarantee to be larger than those sums composed by old unused states.
pq.add(new Pair(newState, newSum));
}
}
}
result.add(currentSum);
n--;
}
return result;
}
让我解释一下我是如何得出解决方案的：
- 我的答案中的 while 循环执行 N 次，考虑使用最大堆（优先队列）。
- 使用复杂度为 O(log(sumOfListLength)) 的 Poll 操作 1 次，因为堆中的最大元素对是 sumOfListLength。
- 插入操作可能最多执行 K 次，每次插入的复杂度为 log(sumOfListLength)。因此，复杂度为 O(N * log(sumOfListLength))。
- Long Tran
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接