Given a magic number sum, to find if there are two numbers whose sum equals to the number

View previous topic View next topic Go down

Given a magic number sum, to find if there are two numbers whose sum equals to the number

Post  yangwenzhou on Fri Sep 23, 2011 11:59 am

Two solutions:

O(n): Traverse the array, put (array[i],sum-array[i]) into the hashtable, then traverse again, if array[i] in the hashtable, it means there are two numbers in the array.

O(1): 每store一个数n,就用n和每个已经存在数据结构中的数字想加求和,将这个和作为key
插入hashtable中,比如首先是empty,依次存入以下数,相对应的hashtable的key:

insert 2 -> ht: empty,
insert 3 -> ht: 5 (2+3)
insert 10 -> ht: 5, 12(2+10), 13(3+10)
insert 1 -> ht: 5, 12, 13, 3, 4, 11
insert 7 -> ht: 5, 12, 13, 3, 4, 11, 9, 10, 17, 8
。。。

more space but faster

yangwenzhou

Posts : 5
Join date : 2011-09-23

View user profile

Back to top Go down

Re: Given a magic number sum, to find if there are two numbers whose sum equals to the number

Post  Admin on Fri Sep 23, 2011 10:22 pm

I have a question about second one.

The big O for O(1) is only the process of checking from the hashset, but for creating the hashset it still need O(n2).

Also I'm not sure how to print the pair of elements that added to sum from the second method.

Shocked


yangwenzhou wrote:Two solutions:

O(n): Traverse the array, put (array[i],sum-array[i]) into the hashtable, then traverse again, if array[i] in the hashtable, it means there are two numbers in the array.

O(1): 每store一个数n,就用n和每个已经存在数据结构中的数字想加求和,将这个和作为key
插入hashtable中,比如首先是empty,依次存入以下数,相对应的hashtable的key:

insert 2 -> ht: empty,
insert 3 -> ht: 5 (2+3)
insert 10 -> ht: 5, 12(2+10), 13(3+10)
insert 1 -> ht: 5, 12, 13, 3, 4, 11
insert 7 -> ht: 5, 12, 13, 3, 4, 11, 9, 10, 17, 8
。。。

more space but faster

Admin
Admin

Posts : 131
Join date : 2011-08-16

View user profile http://codefornongeek.forumotion.com

Back to top Go down

View previous topic View next topic Back to top

- Similar topics

 
Permissions in this forum:
You cannot reply to topics in this forum