从每对的总和中找出第 k 个总和

Question

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

示例输入

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

 3 6
 1 4 6

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

2 5 5 7 7 8 10 10 12

前三个元素生成如下

1+1=2
1+4 = 5
4+1 = 5

编辑：我想到这个主要问题是找到元素总和的地方。我举个例子更清楚。

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

2 5 5 8 11 11 14 14 20

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

Answer 1

编辑：这是 O(n^2)

我理解的问题，第一行第一个数字是数字的个数，第二个数字是k。

您可以使用 PriorityQueue 来解决这个问题，它会在您输入数字时为您排序所有内容。使用 2 个嵌套的 for 循环，使它们访问每对一次。

    for(int k = 0; k < n; k++){
        for(int j = 0; j <= k; j++){

如果j==k，则将k+j入PriorityQueue一次，否则，入两次求和。然后，遍历 PriorityQueue 以获得第 6 个值。

如果您愿意，将使用完整代码进行编辑。

Answer 2

这可以在 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.

时相同

Answer 3

多亏了juvian解决了难点，我才写出这个方案，评论应该解释一下：

def count_sums_of_at_most(amount, nums1, nums2):

    p1 = 0  # Pointer into the first array, start at the beginning
    p2 = len(nums2) - 1  # Pointer into the second array, start at the end

    # Move p1 up and p2 down, walking through the "diagonal" in O(n)
    sum_count = 0
    while p1 < len(nums1):
        while amount < nums1[p1] + nums2[p2]:
            p2 -= 1
            if p2 < 0:
                # p1 became too large, we are done
                break
        else:
            # Found a valid p2 for the given p1
            sum_count += p2 + 1
            p1 += 1
            continue
        break

    return sum_count

def find_sum(k, nums1, nums2):

    # Sort both arrays, this runs in O(n * log(n))
    nums1.sort()
    nums2.sort()

    # Binary search through all sums, runs in O(n * log(max_sum))
    low = nums1[0] + nums2[0]
    high = nums1[-1] + nums2[-1]
    while low <= high:
        mid = (high + low) // 2
        sum_count = count_sums_of_at_most(mid, nums1, nums2)
        if sum_count >= k:
            high = mid - 1
        else:
            low = mid + 1

    return low

arr = [1, 4, 5, 6]
for k in range(1, 1 + len(arr) ** 2):
    print('sum', k, 'is', find_sum(k, arr, arr))

这会打印：

sum 1 is 2
sum 2 is 5
sum 3 is 5
sum 4 is 6
sum 5 is 6
sum 6 is 7
sum 7 is 7
sum 8 is 8
sum 9 is 9
sum 10 is 9
sum 11 is 10
sum 12 is 10
sum 13 is 10
sum 14 is 11
sum 15 is 11
sum 16 is 12

从每对的总和中找出第 k 个总和

Find the k-th sum from sums of every pair

algorithm

sequences