不行了，TM要笑死我了，她们是在练大招么？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Joke - 肚皮舞运动

不行了，TM要笑死我了，她们是在练大招么？

不行了，TM要笑死我了，她们是在练大招么？# Joke - 肚皮舞运动

j*y2011-02-05 08:02

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

s*a2011-02-05 08:02

2 楼

优美的舞姿

h*32011-02-05 08:02

3 楼

用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

s*s2011-02-05 08:02

4 楼

赞短裙那个MM
多放的开啊
看的正爽
上来一人把一半的镜头挡住
太阳

A*i2011-02-05 08:02

5 楼

n2是指n^2么？
用一个hash table存每一个元素的配对值，需要o(n),
然后遍历hash table一旦配对值hits, 就将相配的俩数拿出来，这也需要o(n)
一共0(2n)

m*o2011-02-05 08:02

6 楼

哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈
这个也太山寨了吧

j*y2011-02-05 08:02

7 楼

对是6对
讲讲hash 怎么做吗？多谢

【在 h*********3 的大作中提到】

:
: 用hash就可以了。
: 但不明白为什么只有5对 5,5, 应该是6对吧。

l*02011-02-05 08:02

8 楼

圣斗士的大招：A.E

j*y2011-02-05 08:02

9 楼

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)

s*s2011-02-05 08:02

10 楼

我过生日的时候请短裙MM
50块钱
跳5次

r*y2011-02-05 08:02

11 楼

hash table怎么处理重复的数呢？

【在 A*****i 的大作中提到】

: n2是指n^2么？
: 用一个hash table存每一个元素的配对值，需要o(n),
: 然后遍历hash table一旦配对值hits, 就将相配的俩数拿出来，这也需要o(n)
: 一共0(2n)

w*r2011-02-05 08:02

12 楼

穿短裙的唱歌的都还好,那个穿橙色棉衣的傻不啦叽地呆在那里干嘛?

A*i2011-02-05 08:02

13 楼

【在 r*******y 的大作中提到】

: hash table怎么处理重复的数呢？

h*n2011-02-05 08:02

14 楼

这个白衣mm太销魂了。

【在 s*****a 的大作中提到】

: 优美的舞姿

c*l2011-02-05 08:02

15 楼

排序　前后２指针遍历下不就行了？

l*e2011-02-05 08:02

16 楼

唱得还是很好，跳得也不赖，都不错

j*y2011-02-05 08:02

17 楼

得到6对? 5,5

【在 c*****l 的大作中提到】

: 排序　前后２指针遍历下不就行了？

T*u2011-02-05 08:02

18 楼

it is very nice!

j*y2011-02-05 08:02

19 楼

还是没有答案？多谢了

j*e2011-02-05 08:02

20 楼

所以说人民群众才是艺术的源泉。建议上春晚。

【在 s*****a 的大作中提到】

: 优美的舞姿

m*l2011-02-05 08:02

21 楼

重看了下，你的问题好像没说清楚
不过试试用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 的大作中提到】

: 还是没有答案？多谢了

s*n2011-02-05 08:02

22 楼

没看到后来还来个半段托马斯全悬吗？

【在 w*******r 的大作中提到】

: 穿短裙的唱歌的都还好,那个穿橙色棉衣的傻不啦叽地呆在那里干嘛?

g*e2011-02-05 08:02

23 楼

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 的大作中提到】

: 还是没有答案？多谢了

C*g2011-02-05 08:02

24 楼

穿裤子的这个伴舞mm出工不出力。
短裙mm很抢眼，把注意力全吸引过去了。

g*s2011-02-05 08:02

25 楼

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<

B*e2011-02-05 08:02

26 楼

传说中雅典娜的叹息？？！！

g*e2011-02-05 08:02

27 楼

是我看错题了，我以为要输出所有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));
: }
: }

s*s2011-02-05 08:02

28 楼

要么是雅典娜之惊叹
要么是叹息之墙
你到底想说哪个？

【在 B********e 的大作中提到】

: 传说中雅典娜的叹息？？！！

j*y2011-02-05 08:02

29 楼

thanks

【在 g***s 的大作中提到】