在O(n)中查找数组中的所有差异

Question

问题:给定排序数组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).哪个是对的？

Answer 1

首先想到的是,您没有使用数组已排序的事实.让我们假设它处于递增的顺序(减少可以类似地处理).

我们也可以使用差异望远镜(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)).这只需要一个pass(O(n)),你也可以跳过重复,这意味着跳过a_iif 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).

Answer 2

例如,对于与该元素的数组{2 ¹,2 ²,...,2 ^Ñ }有N·(N-1)/ 2可能存在的差异,也没有两个是相等的.所以存在O(n ²)个差异.

由于您必须枚举所有这些,因此您还需要至少O(n ²)次.