找出O（n）中数组的所有差异 [英] Find all differences in an array in O(n)

问题描述

问题：给定一个排序数组A，找到与A元素所有可能的差异。

我的解决方案：

< （int i = 0; i {（int j = i + 1; j {
System.out.println（Math.abs（ai-aj））;
}
}


当然，它是O（n ^ 2），但是我一点都不算数。我在网上看了一下，发现： http://www.careercup.com/question?id=9111881 。它说您不能做得更好，但是在一次采访中，我被告知您可以做O（n）。

解决方案

首先想到的是，您没有使用对数组进行排序的事实。假设它是按升序排列的（可以类似地处理降幅）。

我们还可以使用差异望远镜（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 = 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）。

Question: Given a sorted array A find all possible difference of elements from A.

My solution:

for (int i=0; i<n-1; ++i) {
  for (int j=i+1; j<n; ++j) {
    System.out.println(Math.abs(ai-aj));
  }
}

Sure, it's O(n^2), but I don't over count things at all. I looked online and I found this: http://www.careercup.com/question?id=9111881. It says you can't do better, but at an interview I was told you can do O(n). Which is right?

解决方案

A first thought is that you aren't using the fact that the array is sorted. Let's assume it's in increasing order (decreasing can be handled analogously).

We can also use the fact that the differences telescope (i>j):

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

Now build a new sequence, call it s, that has the simple difference, meaning (a_i - a_(i-1)). This takes only one pass (O(n)) to do, and you may as well skip over repeats, meaning skip a_i if a_i = a_(i+1).

All possible differences a_i-a_j with i>j are of the form s_i + s_(i+1) + ... + s_(j+1). So maybe if you count that as having found them, then you did it in O(n) time. To print them, however, may take as many as n(n-1)/2 calls, and that's definitely O(n^2).

这篇关于找出O（n）中数组的所有差异的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！