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的元素的乘法而不是附加。不便之處，任何人。