在一个未排序的数组中找到一对差值为输入值'k'的数字。

Question

如标题所述，我想要找到差为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

我已经阅读了SO中以前的帖子 "在数组中找到加和为给定值的数对"

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

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

是否有任何与数学相关的技术可以在O(n)内得到解决方案。 任何帮助都将不胜感激。

- Imposter

Answer 1

你可以用哈希表以O(n)的时间复杂度来完成它。将所有的数字放入哈希表中（O(n)），然后再次遍历数组，查找 number[i]+k 是否存在于哈希表中。哈希表返回 "Yes" 或 "No" 的时间复杂度为 O(1)，由于需要遍历所有数字，所以总的时间复杂度是 O(n)。除哈希表外，任何具有 O(1) 设置和 O(1) 查找时间的集合结构都可以使用。

- Sergey Kalinichenko

---

任何具有O(1)设置和O(1)检查时间的集合结构都可以替代哈希表。这意味着，如果您需要在数据结构中存储键值对，并且需要快速地插入、查找或删除元素，则可以使用具有相同时间复杂度的其他数据结构来实现相同的功能。例如，数组、链表或平衡树等数据结构都可以用作哈希表的替代品，具体取决于您的需求和应用场景。 - Imposter

@冒牌者 你需要一个实现数学集合语义的数据结构。有几种实现方式 - 你可以使用列表，在添加项时每次检查是否存在一个数字，以达到O（N）的效率；使用排序列表和检查O（LogN），或者使用哈希表或标志数组的O（1）。请注意，尽管标志数组的使用成本为O（1），但其初始化成本为O（max（value [0..N]））。 - Sergey Kalinichenko

Answer 2

一种简单的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++;
  }
}

这个解决方案不像使用哈希表的解决方案那样使用额外的空间。

- Thomash

---

我们是否有任何技术，可以不需要对数组进行排序...也许是分治技术...我不知道为什么，但我仍然坚信它可以使用分治规则（递归）来解决。您能否请看一下以下程序..."http://stackoverflow.com/questions/10441237/missed-logic-in-finding-sum-using-recurssion-got-segfault" 我找不到我的逻辑错误在哪里。 - Imposter

这个排序算法使用分治技术。我相信如果不使用额外的存储空间，你很难做得更好。 - Thomash

@Thomash 你的 find_pairs() 函数的复杂度是多少？ - sleeping_dragon

@Thomash 这对于包含重复整数的数组有效吗？例如 [1 1 1 2 3] 并且 k=0。 - sleeping_dragon

这是一个优雅的解决方案，而且你还在代码中展示了如何实现。鼓掌！ - federico verchez

Answer 3

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

• 使用由输入列表索引的布尔数组arr
• 对于每个整数i在输入列表中，则设置arr[i] = true
• 从最小整数到最大整数遍历整个arr，如下所示：
  • 每当您在第i个索引处找到一个true时，请记下此索引。
  • 查看是否存在arr[i+k]为真。如果是，则i和i+k数字是所需的一对
  • 否则继续下一个整数i+1

- phoxis

---

这不是一个好的解决方案。拿一个只有两个元素的数组 {5, 150000} 和 k=149995 举例，你需要使用一个大小为150k的布尔数组来处理它。 - P.P

同意。问题将取决于整数的范围和分布。需要某些映射函数。我认为@dasblinkenlight的哈希解决方案更好。 - phoxis

@KingsIndian我不会轻易将这个解决方案视为“不好”：如果您已经拥有大量的内存，那么如果它可以帮助您加速计算，没有理由不使用它：当项目数量很高且最大项目相对较小时，这个解决方案完胜哈希表！当然，在做出这样的选择时需要良好的判断力，但是“以内存换取速度”的权衡在今天听起来毫无疑问🙂 - Sergey Kalinichenko

如果范围较小（例如8位整数），那么这种方法可能比您创建哈希表并占用更少的空间更快地找到答案。 - Brendan

@dasblinkenlight，这就是为什么我没有投反对票，而是评论了缺陷。因为我认为这仍然是一个有效的解决方案。 :) - P.P