14

如标题所述，我想找到差异为K的元素对 

example k=4 and a[]={7 ,6 23,19,10,11,9,3,15}
output should be :
   7,11
   7,3
   6,10
   19,23
   15,19
   15,11

我已经阅读了之前的帖子“在数组中找到添加到给定总和的数字对”

为了找到一个有效的解决方案，需要多少时间？是时间复杂度O(nlogn)还是O(n)？我试图通过分而治之的技术来做到这一点，但我没有得到任何退出条件的线索......

如果一个有效的解决方案包括对输入数组进行排序和使用两个指针操作元素，那么我认为我应该采取最少的O(nlogn)......

是否有任何与数学相关的技术可以带来解决方案O(n)。任何帮助表示赞赏..

4

3 回答 3

22

You can do it in O(n) with a hash table. Put all numbers in the hash for O(n), then go through them all again looking for number[i]+k. Hash table returns "Yes" or "No" in O(1), and you need to go through all numbers, so the total is O(n). Any set structure with O(1) setting and O(1) checking time will work instead of a hash table.

于 2012-05-04T14:09:19.660 回答
6

O(n*Log(n)) 中的一个简单解决方案是对数组进行排序，然后使用此函数遍历数组：

void find_pairs(int n, int array[], int k)
{
  int first = 0;
  int second = 0;
  while (second < n)
  {
    while (array[second] < array[first]+k)
      second++;
    if (array[second] == array[first]+k)
      printf("%d, %d\n", array[first], array[second]);
    first++;
  }
}

与带有哈希表的解决方案不同，此解决方案不使用额外空间。

于 2012-05-04T14:56:29.807 回答
1

使用 O(n) 中的索引可以完成一件事

  • arr取一个由输入列表索引的布尔数组。
  • 对于每个整数i都在输入列表中，然后设置arr[i] = true
  • 从最小整数到最大整数遍历整个arr，如下：
    • 每当你找到第一个索引时，记下这个索引true。i
    • 看看有arr[i+k]没有真的。如果是，那么i和i+knumbers 是必需的对
    • else 继续下一个整数i+1
于 2012-05-04T14:10:51.530 回答