j**y 发帖数: 462 | 1 array 5,3,7,5,12,5,5
sum 10
output
5,5
3,7
5,5
5,5
5,5
5,5
5,5
no O(n^2)
Thanks | h*********3 发帖数: 111 | 2
用hash就可以了。
但不明白为什么只有5对 5,5, 应该是6对吧 。
【在 j**y 的大作中提到】 : array 5,3,7,5,12,5,5 : sum 10 : output : 5,5 : 3,7 : 5,5 : 5,5 : 5,5 : 5,5 : 5,5
| A*****i 发帖数: 3587 | 3 n2是指n^2么?
用一个hash table存每一个元素的配对值,需要o(n),
然后遍历hash table一旦配对值hits, 就将相配的俩数拿出来,这也需要o(n)
一共0(2n) | j**y 发帖数: 462 | 4 对 是6对
讲讲hash 怎么做吗?多谢
【在 h*********3 的大作中提到】 : : 用hash就可以了。 : 但不明白为什么只有5对 5,5, 应该是6对吧 。
| j**y 发帖数: 462 | 5
5,3,7,5,12,5,5 -> 5,7,3,5,-5,5,5, 然后呢?
【在 A*****i 的大作中提到】 : n2是指n^2么? : 用一个hash table存每一个元素的配对值,需要o(n), : 然后遍历hash table一旦配对值hits, 就将相配的俩数拿出来,这也需要o(n) : 一共0(2n)
| r*******y 发帖数: 1081 | 6 hash table怎么处理重复的数呢?
【在 A*****i 的大作中提到】 : n2是指n^2么? : 用一个hash table存每一个元素的配对值,需要o(n), : 然后遍历hash table一旦配对值hits, 就将相配的俩数拿出来,这也需要o(n) : 一共0(2n)
| A*****i 发帖数: 3587 | 7
【在 r*******y 的大作中提到】 : hash table怎么处理重复的数呢?
| c*****l 发帖数: 879 | | j**y 发帖数: 462 | 9 得到6对? 5,5
【在 c*****l 的大作中提到】 : 排序 前后2指针遍历下不就行了?
| j**y 发帖数: 462 | | | | m********l 发帖数: 4394 | 11
重看了下, 你的问题好像没说清楚
不过试试用Chained Hash了吗?
1) create the hash table.
2) create a link-list node that stores the position of the value
3) put the values inside the hash table. Preferably, during insertion,
you want LIFO
4) loop thru the array again
4.1) get hash[sum-value]
4.2) print if the position of the hash value is greater than current
value's position.
4.3) if position > node->position, continue;
=============
Yes, it's a hack.
why do they test you on procedural stuff when all they teach you in
school is OOP?
【在 j**y 的大作中提到】 : 还是没有答案?多谢了
| g**e 发帖数: 6127 | 12 let me give u an example, 5,5,5,5,5,5; sum=10
there is no way to do it less than O(n^2). This is the worst case.
this structure will help you: HashMap>
【在 j**y 的大作中提到】 : 还是没有答案?多谢了
| g***s 发帖数: 3811 | 13 i dont know why Hashmap doesn't work. maybe i mis-
understand the question?
void findPairs(int[] array, int sum) {
HashMap map = new HashMap();
for (int num : array){
if (map.containsKey(sum - num)){
for (int i = 0; i< map.get(sum-num); i++){
System.out.println(num + "," + (sum-num));
}
}
map.put(num, map.containsKey(num)? map.get(num)+1 : 1);
}
}
the time is O(n+L) L is the pair num of output.
if L< | g**e 发帖数: 6127 | 14 是我看错题了,我以为要输出所有index呢,所以value用了个LinkedList,
原来只是输出元素就可以了
【在 g***s 的大作中提到】 : i dont know why Hashmap doesn't work. maybe i mis- : understand the question? : void findPairs(int[] array, int sum) { : HashMap map = new HashMap(); : for (int num : array){ : if (map.containsKey(sum - num)){ : for (int i = 0; i< map.get(sum-num); i++){ : System.out.println(num + "," + (sum-num)); : } : }
| j**y 发帖数: 462 | 15 thanks
【在 g***s 的大作中提到】 : i dont know why Hashmap doesn't work. maybe i mis- : understand the question? : void findPairs(int[] array, int sum) { : HashMap map = new HashMap(); : for (int num : array){ : if (map.containsKey(sum - num)){ : for (int i = 0; i< map.get(sum-num); i++){ : System.out.println(num + "," + (sum-num)); : } : }
|
|