我有一个未排序的向量V , |V| = N，我需要K-th在已排序的向量中找到元素
S = {V[i] + V[j] | 0 <= i,j < N}, |S| = N*N
我想，以升序排序V，然后只计算第一个K从要素S或降序排列，并计算(N * N) - K是否K > (N * N) / 2但是
N = 50.000 and K = 2.265.604.247
从Java到1迭代需要0.2秒，N*N-K而我最多需要0.3秒。有人可以提示我如何执行此操作吗？
这是我对解决方案的想法。
我认为它应该比计算一切都快得多，您应该考虑一下。
V是对向量长度排序的n，我们想找到k最大的笛卡尔积VxV = {v1+v2|,v1,v2∈V}。
我们将使用类似于二进制搜索的搜索方法来查找通缉电话号码。
注意：
对于每个数字M，M = m+m, m < max{v|v∈ V}我们定义set X = {x ∈ VxV, x<=m+m=M}。很容易找到|X|并max{X}使用它：
Vwith索引i。v = V[i]，v' = M-V[i]。jso：w = V[j] <= v'和j+1>n OR V[j+1] > v'。i，将所有计算出的总和相加j。那是中的数字元素X。max{X}是v+w每对i和所计算出的最大值j，因此您也需要记住它。通过选择不同的值M（使用二进制搜索方法），您可以找到Mfor的值|X| = k。找到它之后，max{X}就是您的解决方案。
V 的元素的乘法 而不是加法。不便之处，敬请原谅。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句