algorithm - 在求和数组中找到第 k 个数

Question

给定一个包含 N 个元素的数组 A，我需要找到对 (i,j) 使得 i 不等于 j 并且如果我们为所有对 (i, j) 然后它来到第k个位置。

示例:让 N=4 和数组 A=[1 2 3 4] 如果 K=3 那么答案是 5 因为我们可以清楚地看到总和数组变成这样:[3 ,4,5,5,6,7]

我不能把所有的 i 和 j 都放在一起，因为 N 可以达到 100000。请帮忙解决这个问题

我的意思是这样的:

int len=N*(N+1)/2;
int sum[len];
int count=0;
for(int i=0;i<N;i++){
   for(int j=i+1;j<N;j++){
        sum[count]=A[i]+A[j]; 
        count++;
   }
}
//Then just find kth element.

我们不能采用这种方法

Answer 1

基于以下事实的解决方案 K <= 50 : 让我们先看第一个 K + 1排列顺序排列的数组元素。现在我们可以尝试他们所有的组合。正确性证明:假设一对 (i, j)是答案，其中 j > K + 1 .但是有K具有相同或更小总和的对:(1, 2), (1, 3), ..., (1, K + 1) .因此，它不能是 K -th 对。

有可能实现 O(N + K ^ 2)通过选择 K + 1 的时间复杂度使用 quickselect 的最小数字算法(可以做得更好，但不是必需的)。您也可以仅使用数组并获得 O(N * log N + K ^ 2 * log K)复杂性。