你有一个数字的升序列表，你能想到的最有效的算法是获取该列表中每两个数字之和的升序列表。结果列表中的重复项无关紧要，您可以删除它们或根据需要避免它们。
需要明确的是，我对算法感兴趣。随意以您喜欢的任何语言和范式发布代码。
问问题
3403 次
8 回答
12
截至 2018 年的编辑：您可能应该停止阅读此内容。（但我不能删除它，因为它被接受了。）
如果你这样写出总和：
1 4 5 6 8 9
---------------
2 5 6 7 9 10
8 9 10 12 13
10 11 13 14
12 14 15
16 17
18
你会注意到，由于 M[i,j] <= M[i,j+1] 和 M[i,j] <= M[i+1,j]，那么你只需要检查左上角“角”并选择最低的一个。
例如
- 只有 1 个左上角，选择 2
- 只选1个，选5个
- 6或8，选6
- 7或8，选7
- 9或8，选8
- 9或9，两个都选：）
- 10 或 10 或 10，选择所有
- 12 或 11，选择 11
- 12 或 12，两个都选
- 13 或 13，两个都选
- 14 或 14，两个都选
- 15 或 16，选择 15
- 只有 1 个，选择 16 个
- 只有1个，选17个
- 只有 1 个，选择 18 个
当然，当你有很多左上角时，这个解决方案就会下放。
我很确定这个问题是 Ω(n²)，因为你必须计算每个 M[i,j] 的总和——除非有人有更好的求和算法:)
于 2008-09-18T21:41:13.387 回答
4
我认为我将逐步对其进行伪编码并解释我的逻辑，而不是对其进行编码，以便更好的程序员可以在必要时在我的逻辑中戳出漏洞。
第一步，我们从长度为 n 的数字列表开始。对于每个数字，我们需要创建一个长度为 n-1 的列表，因为我们没有向自身添加数字。最后，我们有一个大约在 O(n^2) 时间内生成的排序列表的列表。
step 1 (startinglist)
for each number num1 in startinglist
for each number num2 in startinglist
add num1 plus num2 into templist
add templist to sumlist
return sumlist
在第 2 步中，因为列表是按设计排序的（向已排序列表中的每个元素添加一个数字，列表仍将被排序），我们可以通过将每个列表合并在一起而不是对整个列表进行合并排序来简单地进行合并排序。最后，这应该花费 O(n^2) 时间。
step 2 (sumlist)
create an empty list mergedlist
for each list templist in sumlist
set mergelist equal to: merge(mergedlist,templist)
return mergedlist
然后，合并方法将是正常的合并步骤，并检查以确保没有重复的总和。我不会写出来，因为任何人都可以查找合并排序。
所以这就是我的解决方案。整个算法是 O(n^2) 时间。随时指出任何错误或改进。
于 2008-08-03T23:06:15.443 回答
2
您可以在 python 的两行中使用
allSums = set(a+b for a in X for b in X)
allSums = sorted(allSums)
迭代的成本是n^2（可能是集合的额外对数因子？），排序的成本是 s * log(s)，其中 s 是集合的大小。
集合的大小可能与n*(n-1)/2例如 if一样大X = [1,2,4,...,2^n]。所以如果你想生成这个列表，至少n^2/2在最坏的情况下需要，因为这是输出的大小。
但是，如果您想选择结果的前 k 个元素，您可以使用X+YFrederickson 和 Johnson 的排序矩阵选择算法在 O(kn) 中执行此操作（有关血腥细节，请参见此处）。尽管这可能可以修改为通过重用计算在线生成它们并为此集合获得一个有效的生成器。
@deuseldorf，Peter(n!)我严重怀疑 deuseldorf 的意思是“n 阶乘”而只是“n，（非常兴奋）！”
于 2008-08-11T14:47:31.227 回答
1
我能想到的最好的办法是生成每对总和的矩阵，然后将行合并在一起，a-la 合并排序。我觉得我错过了一些简单的见解，这些见解将揭示一个更有效的解决方案。
我的算法，在 Haskell 中：
matrixOfSums list = [[a+b | b <- list, b >= a] | a <- list]
sortedSums = foldl merge [] matrixOfSums
--A normal merge, save that we remove duplicates
merge xs [] = xs
merge [] ys = ys
merge (x:xs) (y:ys) = case compare x y of
LT -> x:(merge xs (y:ys))
EQ -> x:(merge xs (dropWhile (==x) ys))
GT -> y:(merge (x:xs) ys)
我发现了一个小的改进，它更适合基于惰性流的编码。不要成对合并列，而是一次合并所有列。优点是您立即开始获取列表的元素。
-- wide-merge does a standard merge (ala merge-sort) across an arbitrary number of lists
-- wideNubMerge does this while eliminating duplicates
wideNubMerge :: Ord a => [[a]] -> [a]
wideNubMerge ls = wideNubMerge1 $ filter (/= []) ls
wideNubMerge1 [] = []
wideNubMerge1 ls = mini:(wideNubMerge rest)
where mini = minimum $ map head ls
rest = map (dropWhile (== mini)) ls
betterSortedSums = wideNubMerge matrixOfSums
但是，如果您知道您将使用所有的总和，并且早点获得其中一些没有优势，请使用 ' foldl merge []'，因为它更快。
于 2008-08-03T21:36:25.890 回答
1
在 SQL 中：
create table numbers(n int not null)
insert into numbers(n) values(1),(1), (2), (2), (3), (4)
select distinct num1.n+num2.n sum2n
from numbers num1
inner join numbers num2
on num1.n<>num2.n
order by sum2n
C# LINQ：
List<int> num = new List<int>{ 1, 1, 2, 2, 3, 4};
var uNum = num.Distinct().ToList();
var sums=(from num1 in uNum
from num2 in uNum
where num1!=num2
select num1+num2).Distinct();
foreach (var s in sums)
{
Console.WriteLine(s);
}
于 2008-08-08T23:05:47.057 回答
1
这个问题已经困扰我大约一天了。惊人的。
无论如何，您不能轻易摆脱它的 n^2 特性，但是您可以在合并方面做得更好，因为您可以限制插入每个元素的范围。
如果您查看您生成的所有列表，它们具有以下形式：
(a[i], a[j]) | j>=i
如果你把它翻转 90 度，你会得到：
(a[i], a[j]) | i<=j
现在，合并过程应该采用两个列表i和i+1（对应于第一个成员总是a[i]和的列表），您可以通过位置和位置a[i+1]绑定范围以将元素(a[i + 1], a[j])插入列表。i(a[i], a[j])(a[i + 1], a[j + 1])
这意味着您应该在j. 我不知道（还）你是否也可以利用这一点j，但这似乎是可能的。
于 2008-08-21T18:16:13.800 回答
1
无论您做什么，如果没有对输入值的额外限制，您都不会比 O(n^2) 做得更好，因为您必须遍历所有数字对。迭代将主导排序（您可以在 O(n log n) 或更快的时间内完成）。
于 2008-09-18T22:15:18.577 回答
-4
如果你正在寻找一个真正与语言无关的解决方案，那么我认为你会非常失望，因为你会被 for 循环和一些条件所困。但是，如果您将其打开到函数式语言或函数式语言特性（我正在查看您的 LINQ），那么我的同事在这里可以用 Ruby、Lisp、Erlang 等的优雅示例填充此页面。
于 2008-08-03T21:24:56.160 回答