查找为O（n）

问题阵列中的所有差异：给定一个有序数组A找到A.元素的所有可能差异查找为O（n）

我的解决办法：

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）。哪个是对的？

2011-12-10 WisaF

我会小心的，在这家公司采取了工作......他们可能会期望你解决NP完全问题P时间... ;-) –

我的猜测是，你或面试官忽视或无意中听到一个额外的条件。 –

将n定义为差异的数量（输出的大小而不是输入的大小）。嘿presto - 现在是O（n）。 – Steve314

首先想到的是，您没有使用数组排序的事实。我们假设它的顺序是递增的（递减可以类似地处理）。

我们也可以用事实差异望远镜（I> j）的：具有简单的区别，这意味着(a_i - a_(i-1))

a_i - a_j = (a_i - a_(i-1)) + (a_(i-1) - a_(i-2)) + ... + (a_(j+1) - a_j)

现在建立一个新的序列，称之为s和。这只需要一次传球（O(n)），你可以跳过重复，意思是跳过a_i如果a_i = a_(i+1)。

所有可能的差异a_i-a_j与i>j的形式是s_i + s_(i+1) + ... + s_(j+1)。所以也许如果你把它看作是发现它们的话，那么你在O(n)的时间就完成了。然而，要打印它们，可能需要多达n(n-1)/2的电话，这绝对是O(n^2)。

2011-12-10 05:21:25 PengOne

好的。我看到这是如何使用数组排序的事实，因为您不必担心绝对值。我仍然不认为这真的是O（n），但这可能是他想到的。谢谢 – WisaF

例如用于与所述元件数组{2 ，2 ，...，2 ^Ñ}有⋅Ñ（N-1）/ 2可能的差异，没有两个是平等的。所以有O（n ）的差异。由于你必须列举所有这些，你至少还需要O（n ）时间。

2011-12-10 05:19:53 sth

这就是我给出的链接中的答案，但面试官坚持认为有O （n）解决方案。 – WisaF

由于'a [last] - [first]是最大可能的差异，所以它也是（一个小于）最大可能数量的差异值。所以这在某些方面是线性的，而不是原始数组的大小。也许有一种方法可以检查每个差异实际上是否在时间上与潜在差异的数量成线性关系，但我无法想象ATM。 – Steve314

是的，O（n^2）是最糟糕的情况，但请注意，有些差异可能会多次出现。问题出现了：是否有一个输出敏感算法，具有O（k）时间复杂度（或类似），其中k是唯一差异的数量？这意味着例如对于其中k = O（n）的特殊输入，该算法将只需要O（n）。 –

排序或无序不要紧，如果你要计算每个区别是没有办法做到这一点，在不到N^2，

有人问错了，或者你只是做为O（n ），然后打印42另外N次：D

2011-12-10 05:53:50 jackdoe

您可以通过假定数组内容在排序前是随机整数来获得另一个计数器示例。那么Ai - Aj与Ak - Al，甚至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个元素是非零的。

2011-12-10 08:22:46 mcdowella

如果面试官喜欢理论游戏，也许他正在考虑使用输入和结果表？任何问题与输入大小的限制，并有一个已知的解决方案，可以通过表查找解决。鉴于您已经首先创建并存储了该表，该表可能是大。

所以如果数组的大小是有限的，这个问题可以通过表查找来解决，这个问题甚至可以在一定的时间内完成。即使最大阵列大小为两个（假设是32位整数），表格也不适合正常计算机的内存或磁盘。对于阵列的更大的最大尺寸，您将陷入“不适合已知宇宙”的大小。但是，从理论上讲，这是可以做到的。

（但在现实中，我认为，延Gustedt的评论更容易。）

2011-12-10 10:21:10

回答