找对数字的区别是输入值'K'在一个未排序数组 [英] find pair of numbers whose difference is an input value 'k' in an unsorted array

问题描述

正如标题，我想找到的元素，其不同之处的成对的 K

As mentioned in the title, I want to find the pairs of elements whose difference is 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

我已经阅读了previous职位，因此，<一href="http://stackoverflow.com/questions/8334981/find-pair-of-numbers-in-array-that-add-to-given-sum">find对数字的阵列添加到给定的总和

为了找到一个有效的解决方案，有多少时间没有考虑？是的时间复杂度 O（nlogn）或 O（N）？ 我试图通过分而治之的方法来做到这一点，但我没有得到的退出条件的任何线索......

In order to find an efficient solution, how much time does it take? Is the time complexity O(nlogn) or O(n)? I tried to do this by a divide and conquer technique, but i'm not getting any clue of exit condition...

如果一个有效的解决方案，包括整理输入数组，并用两个指针操作件的话，我想我应该采取最低的O（nlogn） ...

If an efficient solution includes sorting the input array and manipulating elements using two pointers, then I think I should take minimum of O(nlogn)...

有没有数学相关的技术，它带来了 O解决方案（N）。任何帮助是AP preciated ..

Is there any math related technique which brings solution in O(n). Any help is appreciated..

推荐答案

您可以在O（n）的利用哈希表做到这一点。把所有号码的哈希为O（n），然后再通过他们又都在寻找号[I] + K 。哈希表返回是或否O（1），你需要经过所有的数字，所以总为O（n）。任何一组结构O（1）制定和O（1）检查时间将工作哈希表来代替。

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.

这篇关于找对数字的区别是输入值'K'在一个未排序数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！