arrays - 当 A 和 B 排序时找到最小的 A[i]^2 + B[i]^2

Question

给定两个数组 A 和 B，长度为 n。 A 是升序排列的，B 是降序排列的。查找“乘积”A[i]^2 + B[i]^2 最小的索引 i。

我需要一个 O(log(n)) 的解决方案，这是所需的复杂度。

案例:

>>> A
[0, 4, 10, 12, 17, 28, 31, 32, 35, 39]
>>> B
[39, 34, 34, 31, 27, 23, 19, 11, 3, 2]

这里“乘积”被最小化了 i=4

>>> [A[i]**2 + B[i]**2 for i in range(10)]
[1521, 1172, 1256, 1105, 1018, 1313, 1322, 1145, 1234, 1525]
>>> min(range(10), key=lambda i: A[i]**2 + B[i]**2)
4

Answer 1

在我看来，您的问题的答案是否定的，线性算法是最快的。

建设性地，我们可以构建任意长度的序列，在该序列内的任意随机位置具有最大值。此外，基于这些序列构建的平方和序列是无序的，因此您不能使用适用于排序序列的二进制搜索等技术。

例如，如果我们有两个长度为 7 的数组:

5   8   10  11  12  14  15
12  11  10  9   7   6   1

我们得到这样的平方和数组:

169  185  200  202  193  232  225

我们可以看到，最大值是 232，但是除了遍历整个数组之外没有办法找到它，因为平方和序列未排序并且最大值位于内部某处。

此外，使用一个数组已排序这一事实是无用的，因为第二个数组会对总和产生很大影响，并且在单个数组上使用二进制搜索之类的方法来尝试计算总和是没有意义的。

我敢肯定，这个问题等同于在未排序的数组中找到最大的元素，该元素的线性解最快。