寻找整数数组中和相等的数字对的算法。
例如 {1 2 3 4 6},输出应为 {3 2} 和 {4 1},因为它们的和都是5。
主要问题在于复杂度应该是O(n)。如果我们找到了解决方案,请帮忙。
寻找整数数组中和相等的数字对的算法。
例如 {1 2 3 4 6},输出应为 {3 2} 和 {4 1},因为它们的和都是5。
主要问题在于复杂度应该是O(n)。如果我们找到了解决方案,请帮忙。
您确定问题在O(n)时间内可以解决吗?
想象一下输入序列只是{0, 0, 0, 0, 0, 0, ..., 0}的情况。这里每两个对都满足条件。仅列出所有对已经至少需要O(n^2)的时间。
OP
没有澄清确切的问题,OP
的示例表达了另一件事。有两个2对(如@Dialecticus所说),而OP
只提到其中一个。 - Saeed Amirisum = 5
array = {1,2,3,4,6}
for every i in array{
if i>=sum:
continue
if tmp[i] != 0 {
output {i,(sum-i)}
tmp[i] = 0
continue
}
tmp[sum-i] := i
}
就是这样。非常简单,时间复杂度为O(n)。
缺点:
我不确定是否能够有效地完成这个任务。
根据给定的信息,数组未排序且您不知道需要遍历数组两次才能得到期望的总和。
考虑一种搜索算法。最简单的线性(顺序)搜索具有O(n)的复杂度。它只是用于遍历数组。如果您知道期望的总和,则情况类似,实际上您需要做的就是线性搜索。对于其他任何事情,您都会得到更高的复杂度。
但在您的情况下,您不知道总和,因此您需要多次遍历。我的想法是这是O(n log n)或O(n^2)。
也许有一种解决方案可以利用更多的数据结构,例如求和表格(2D数组???),但存在这样的解决方案的机会很低。