algorithm - 两个排序数组中的第 K 个最小 SUM - 二进制搜索解决方案

Question

我正在尝试解决面试练习题。

问题是:

Given two integer arrays sorted in ascending order and an integer k. Define sum = a + b, where a is an element from the first array and b is an element from the second one. Find the kth smallest sum out of all possible sums.

For example

Given [1, 7, 11] and [2, 4, 6].

For k = 3, return 7.

For k = 4, return 9.

For k = 8, return 15.

我们定义 n 为 A 的大小，m 为 B 的大小。 我知道如何使用堆来解决它(O(k log min(n，m，k))时间复杂度)。但是问题表明还有另一种二进制搜索方法可以使用 O( (m + n) log maxValue) 来完成，其中 maxValue 是 A 和 B 中的最大值。任何人都可以给出一些使用 binary 解决它的评论搜索?

我的想法是我们可以用x = A[] + B[]作为搜索对象，因为第k个x就是我们想要的。如果是这样，如何在二进制搜索中更新 x？如何检查更新后的 x 是否有效(这样的一对是否真的存在)？

谢谢

原来的问题在这里: https://www.lintcode.com/en/problem/kth-smallest-sum-in-two-sorted-arrays/

Answer 1

可以求解二分查找和滑动窗口，时间复杂度O((N + M) log maxvalue) .

让我们考虑解决这个问题(我称之为计数问题)。

You are given integers N, M, S, sequences a and b.
The length of sequence a is exactly N.
The length of sequence b is exactly M.
The sequence a, b is sorted.
Please calculate the number of pairs that satisfies a[i]+b[j]<=S (0<=i<=N-1, 0<=j<=M-1).

实际上，这个计数问题可以解决O(N log M)中的二分查找时间。
令人惊讶的是，这个问题可以解决 O(N+M) .

二分搜索算法
可以求解满足a[i] + b[x] <= S --> b[x] <= S - a[i]的x的最大值对于 O(log M) .
因此，可以求解出O(log M)的x值的个数。因为它等于 x+1。

O(N+M) 算法
实际上，如果你这样做 i++ ，x 的值等于或小于 x 的先前值。
所以可以使用滑动窗口算法和。
您可以求解 O(N+M)，因为您必须执行操作 i++ N次，并运行x-- M 次。

解决这个主要问题
你可以 binary_search 寻找 S 并且你可以解决不等式 (counting problem's answer <= K) .
答案是S的最大值。
时间复杂度为O((N + M) log maxvalue) .