找到一对数字，其差别是未排序数组中的输入值’k’

正如标题中所提到的，我想找到差异为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中的先前post“ 在数组中找到添加到给定总和的数字对 ”

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

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

是否存在任何与O(n)相关的数学相关技术。 任何帮助表示赞赏..

Answer 1

您可以使用哈希表在O（n）中执行此操作。 将所有数字放在O（n）的哈希值中，然后再次遍历它们，查找number[i]+k 。 哈希表在O（1）中返回“是”或“否”，您需要遍历所有数字，因此总数为O（n）。 任何具有O（1）设置和O（1）检查时间的集合结构都将起作用而不是哈希表。

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++; } } 

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

Answer 3

在O（n）中使用索引可以完成一件事

• 获取由输入列表索引的布尔数组arr 。
• 对于每个整数， i在输入列表中，然后设置arr[i] = true
• 遍历整个arr从最低整数到最高整数，如下所示：
  • 无论何时在第i个索引处找到true ，请记下此索引。
  • 看看arr[i+k]是否属实。 如果是，则i和i+k数字是必需的对
  • 否则继续下一个整数i+1