我有一个包含 n 个元素的数组,我需要计算两个元素对 (array[i]+array[j]) 的所有 n*n 总和。所有总和按升序排列。我需要找到第 K 个总和
例如:
数组[] = {3,4,5}
所有和:{(3+3),(3+4),(4+3),(3+5),(5+3),(4+4),(4+5),( 5+4),(5+5)}
K = 6
我需要找到第 K 个和的值(在这种情况下,第 6 个和是 4+4,我将返回 8);
解决方案可能是最优的
这是我的解决方案;它不是最佳的:
for(i=0;i<n;i++)
fin>>a[i];
qsort(a, n, sizeof(int), int_cmp);
for(i=0;i<n;i++)
for(j=i;j<n;j++)
{
sum[k]=a[i]+a[j];
if(i!=j)
sum[++k]=a[i]+a[j];
k++;
}
qsort(sum, n*n, sizeof(int), int_cmp);
cout<<sum[nrs-1];
最佳答案
我从谷歌面试问题中看到了类似的问题,因为他们使用两个排序数组而不是一个,但解决方案有效。可以给出一个将在 O(klogk)
中工作的优化这里。
要在这种情况下找到最大值,必须计算出所有小于它的值,即让 i,j
成为您的情况下的最大值 5,5
要将 5,5
视为最大值,有必要评估 4,5
和 5,4
。即 i-1,j
和 i,j-1
所以一个工作代码将是在 c++ 中使用一个 heap
它是一个 priority queue
。代码如下
#include <iostream>
#include <queue>
using namespace std;
for(i=0;i<n;i++)
fin>>a[i];
qsort(a, n, sizeof(int), int_cmp);
std::priority_queue<int > heap;
heap.add(pair(n-1, n-1)); // biggest pair n=array size
// remove max k-1 times
for (int i = 0; i < k - 1; ++i) {
// get max and remove it from the heap
max = heap.pop();
// add next candidates
heap.push(pair(max.i - 1, max.j));
heap.push(pair(max.i, max.j - 1));
}
// get k-th maximum element
max = heap.pop();
maxVal = a[max.i] + a[max.j];
现在这个优化到 O(k.logk)
还有另一个优化到 O(k)
。你可以在这里找到它。 Kth sum in O(k)
关于c++ - 数组中的第 K 个和,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/29380264/