找到一对数字,其差别是未排序数组中的输入值'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).任何帮助表示赞赏..

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

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