java - 在 n^2*log(n) 时间内具有 4 个数字的 3sum 的变体?

标签 java arrays algorithm big-o

我正在为我所参加的算法类(class)做一个项目,但我完全陷入了僵局。任务是在 O(n^2*log(n)) 时间内找到数组中 i+j=k+l 的所有 4 个数字的集合。

我知道这类似于 3sum 问题,您必须在数组中找到 i+j+k=0 的所有集合。我们在讲座中讨论了这个问题的解决方案,通过迭代所有唯一的 2 对(n^2 次)并在排序数组上使用二进制搜索,在 O(n^2*log(n)) 时间内解决了这个问题找到满足问题的值(log(n) 时间)。

但是,我看不出这次如何解决 4 个数字的问题。我认为这是一个安全的猜测,复杂性中的 log(n) 来自二进制搜索,我将在最后一个搜索中使用它。但是,这意味着我必须在 n^2 时间内迭代 3 的所有可能组合,我认为这是不可能的。

我不是在找人为我做我的工作,但也许如果有人知道如何解决这个问题,他们可以在正确的方向上轻轻敲击我。谢谢。

编辑:注意我需要使用排序来解决这个问题也可能会有所帮助。一旦我这样做了,我必须编写另一个实现,使用散列使其更快,但我认为我自己可以做到这一点。我只需要弄清楚如何首先解决排序问题。

最佳答案

保留总和和对的排序列表。例如,给定列表

[1, 2, 4, 8, 16, 32, 9, 82]

我们将要识别 1+9 = 2+8
确定列表中最大的两个数字,O**(N)**。在这种情况下,它们是 (82, 32),总和为 114。分配一个数组 pair_sum 114 个地点;将所有位置设置为空指针。

现在遍历您的 i, j 对的列表。对于每一对,在索引 i+j 处插入两个数字作为元组值。当你在某个索引处发生冲突时,你就完成了:你找到了第二个对和。

我将在一些不太伪的代码中对此进行概述;你可以翻译成你喜欢的实现语言。

银行 = [1, 2, 4, 8, 16, 32, 9, 82]
尺寸 = 长度(银行)
// Find the two largest numbers and allocate the array ...
pair_sum = array[114], initialize to all nulls

for lo in 0:size-1
    for hi in lo+1:size
        sum = bank[lo] + bank[hi]
        if pair_sum[sum]
            // There is already a pair with that sum
            print pair_sum[sum], "and", bank[lo], bank[hi]
        else
            // Record new sum pair
            pair_sum[sum] = tuple(bank[lo], bank[hi])

这是 O(N^2) ,有界空间取决于数组值。

如果 出于实际原因,您不允许将总和用作索引,我认为您可以将其调整为二进制搜索和插入,从而为您提供 日志(n) 零件。

关于java - 在 n^2*log(n) 时间内具有 4 个数字的 3sum 的变体?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/47077908/

相关文章:

algorithm - 如何在此图上应用 Dijkstra 算法?

algorithm - 关于wiki中加泰罗尼亚数字的表达

java - 数组不能隐式转换为可迭代的

arrays - 使用 Decodable 在 Realm 中保存对象数组

arrays - 在 n 个元素的数组中使用二进制搜索查找 k 个不同的键

Java 彩票数组程序

javascript - Javascript排序数组对象未执行

Java元素明智的求和2数组

java - 无法使用Lambda流过滤器获得响应

java - 将edittext添加到自定义 View 中