在O(n)中查找数组中的所有差异
问:给定一个排序数组A，找出A中所有可能的元素差异。
我的解决方案是：
for (int i=0; i<n-1; ++i) {
for (int j=i+1; j<n; ++j) {
System.out.println(Math.abs(ai-aj));
}
}当然，它是O(n^2)，但我一点也不多算。我在网上看了看，发现了这个：http://www.careercup.com/question?id=9111881。它说你不能做得更好，但在一次面试中，我被告知你可以做O(n)。哪一个是对的？
回答 6
Stack Overflow用户
发布于 2011-12-10 13:21:25
第一个想法是，您没有使用数组已排序的事实。让我们假设它是按递增顺序排列的(递减可以类似地处理)。
我们还可以利用差分望远镜(i>j)：
a_i - a_j = (a_i - a_(i-1)) + (a_(i-1) - a_(i-2)) + ... + (a_(j+1) - a_j)现在构建一个新的序列，命名为s，它有一个简单的区别，意思是(a_i - a_(i-1))。这只需要一遍(O(n))就可以完成，你也可以跳过重复，意思是如果是a_i = a_(i+1)就跳过a_i。
a_i-a_j与i>j的所有可能差异都是s_i + s_(i+1) + ... + s_(j+1)形式的。所以，如果你把它算作找到了它们，那么你就在O(n)时间里找到了它们。然而，要打印它们，可能需要大量的n(n-1)/2调用，这绝对是O(n^2)。
Stack Overflow用户
发布于 2011-12-10 13:53:51
排序或未排序都无关紧要，如果您必须计算每个差值，则无法在小于n^2的时间内完成，
问题被问错了，或者只是做O(n)，然后打印42次其他N次:D
Stack Overflow用户
发布于 2011-12-10 16:22:47
通过在排序前假设数组内容是随机整数，您可以获得另一个反例。那么两个差异，Ai - Aj与Ak -A1，甚至Ai - Aj与Aj - Ak相同的机会太小了，以至于只有O(n)个明显的差异Ai - Aj。
考虑到这一点，面试官的问题是解释允许O(n)解的特殊情况。一种可能是数组值都是0..n范围内的数字，因为在这种情况下，最大绝对差仅为n。
我可以在O(n lg n)中做到这一点，但不能在O(n)中做到。用一个大小为n+1的数组表示数组内容，其中元素i设置为1，其中数组中有值i。然后使用FFT将阵列与其自身进行卷积-存在差异Ai - Aj =k，其中卷积的第k个元素非零。
https://stackoverflow.com/questions/8454573
复制相似问题
腾讯云开发者
