K-个元素N * N和向量

Question

我有一个未排序的矢量V , |V| = N，我需要找到K-th元素排序向量

S = {V[i] + V[j] | 0 <= i,j < N}, |S| = N*N

我想以升序V然后只计算第一从SK元件或降序排序，并计算(N * N) - K如果K > (N * N)/2但对于

N = 50.000 and K = 2.265.604.247

Java中需要0.2秒才能从1重复到N*N-K，我需要在最大0.3秒内完成此操作。有人可以给我一个提示如何做到这一点？

Answer 1

这是我对解决方案的想法。
我认为它应该比计算一切都快很多，而且你应该考虑它。

---

V排序向量长度n，我们希望找到k个最大的笛卡尔积VxV = {v1+v2|,v1,v2∈V}的数量。

我们将使用类似二进制搜索的搜索方法来查找想要的数字。

注意这一点：
对于每一个号码M，M = m+m, m < max{v|v∈ V}我们定义设置X = {x ∈ VxV, x<=m+m=M}。这是很容易找到|X|和max{X}使用此：

1. 循环遍历V索引i。
2. 每v = V[i]，v' = M-V[i]。
3. 使用二进制搜索，找到如下索引j：w = V[j] <= v'和j+1>n OR V[j+1] > v'。
4. 对于每个与i循环，总计所有计算的j。这是X中的数字元素。
5. max{X}是v+w的最大值，计算的每一对i和j，所以你也需要记住它。

通过的M选择不同的值（使用二进制搜索方法），你可以找到它|X| = k的M值。当你找到它时，max{X}是你的解决方案。

---

PS。我删除了我之前的回答，因为它包含我认为我已删除的部分，并且因为我已经将它写入了 V的元素的乘法而不是附加。不便之处，任何人。