时间戳

首页 > 解决方案 > 从每对的总和中找到第 k 个总和

algorithm - 从每对的总和中找到第 k 个总和

问题描述

我得到了具有 n 个元素的数组，我需要在时间复杂度 O(n*logn) 中从每对 n^2 的总和中找到第 k 个总和，总和按升序排列。

示例输入

在第一行中给出了要查找的元素数和总和数。在我们需要生成的对数的第二行列表中。

 3 6
 1 4 6

给定列表的答案是 8，下面是每对和的数组，其中 8，4+4 的和在第 6 位。

2 5 5 7 7 8 10 10 12

其中前三个元素生成如下

编辑：我想到了这个，主要问题是找到元素总和的位置。我将举例说明它更清楚。

对于序列 [1, 4, 10]，我们有

2 5 5 8 11 11 14 14 20

问题是在哪里放置 4+4 的总和，这取决于 1+10 > 4+4，其他总和有固定的位置，因为第二个元素 + 最后一个总是大于最后一个 + 第一个（如果我们有升序的元素） .

标签： algorithmsequences

解决方案

这可以在 O(n log maxSum) 中解决。

伪代码：

sort(array)
low = array[1] * 2
high = array[n] * 2
while (low <= high): (binarySearch between low and high)
    mid = floor((high + low) / 2)
    qty = checkHowManySumsAreEqualOrLessThan(mid)
    if qty >= k:
        high = mid - 1
    else:
        low = mid + 1
answer = low // low will be the first value of mid where qty was >= k. This means that on low - 1, qty was < k. This means the solution must be low

排序是 O(n log n)。二进制搜索成本 log(array[n] * 2 - array[0] * 2)。

checkHowManySumsAreEqualOrLessThan(mid) 可以使用 2 个指针在 O(n) 中完成，如果你不知道怎么做，请告诉我。

这是有效的，因为即使我们没有对 k 进行二进制搜索，如果有 x 和 <= mid，如果 k < x 那么第 k 个和将低于 mid 是真的。当 k > x 时相同。

推荐阅读