作者热门文章
- c - 在位数组中找到第一个零
- linux - Unix 显示有关匹配两种模式之一的文件的信息
- 正则表达式替换多个文件
- linux - 隐藏来自 xtrace 的命令
我有一组 N,对于 N>3,不同的整数,问题是找到给定集合的 3 个子集的所有不同的总和。 3 子集是基数为 3 的子集。
我知道愚蠢的方法是对所有可能的总和进行立方搜索,然后找出所有重复项。有没有更有效的方法来做到这一点?我正在用 C 编程。
编辑:如果说元素的数量增加了,我想知道一个通用的更快的算法。
最佳答案
如果您怀疑您可能有很多重复的总和,那么您可以先计算所有不同的 2 子集总和,然后对于您找到的每个不同的 2 子集总和,跟踪您找到的哪对子集给了您和。如果您所有的数字都不同,那么如果您找到另一对给您相同的总和,您应该将总和标记为“多个”,并且您可以根据需要删除为其存储的那对。现在你有一组 2 子集和,每个和都存储了一对,或者标记为“多个”。对于每个 2 子集总和,如果它被标记为“多个”,那么您将遍历原始集合中的所有数字,并记录您可以通过将每个数字添加到 2 子集总和来形成的所有 3 子集总和。否则,如果 2 子集总和未标记为“多个”并且您有一对 (a,b) 与之关联,那么您将执行相同的操作,只是在迭代原始数字集时跳过 a 和 b .这就是您获得所有不同的 3 子集总和的方式。如果你有 n 个数字并且它们使 N 个不同的 2 子集和,那么如果你在算法的两个阶段使用哈希表来检测重复项,这种方法的复杂度是 O(nN),这可能比蛮力要好得多强制 O(n^3 log n),尤其是当你有一组相当密集的整数时。
关于c - 子集的不同总和数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/17898678/
我是一名优秀的程序员,十分优秀!