leetcode 3sum runtime 一問 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

leetcode 3sum runtime 一問

leetcode 3sum runtime 一問# JobHunting - 待字闺中

r*e2012-07-04 07:07

1 楼

LEETCODE 3SUM 解法
這個是我的N^2 算法
http://pastebin.com/MTJ751ML
二個SOLUTION 都PASS 了 LEETCODE 的TEST，但是有個問題，就是為什麼我的 N^2
算法會比 (N^2)(logn)算法慢？？？
請各位指點一下。

i*e2012-07-04 07:07

2 楼

你的 O(N^2) 用了多余的 hashmap 来去重，其实根本不必要，可以去掉省一些空间和
时间。
给你参考下我的实现：
http://pastebin.com/tYDvbqvj
但是总的来说 n^2 log n 和 n^2 没有可比性，尤其你看large case 的 n 都没有太大
的情况下。要是 n 非常大的话，那时间差别还是会出来的。

r*e2012-07-04 07:07

3 楼

謝謝你

S*12012-07-04 07:07

4 楼

If we can see the test cases? So we can figure out what is the problem?
Thanks

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

: 你的 O(N^2) 用了多余的 hashmap 来去重，其实根本不必要，可以去掉省一些空间和
: 时间。
: 给你参考下我的实现：
: http://pastebin.com/tYDvbqvj
: 但是总的来说 n^2 log n 和 n^2 没有可比性，尤其你看large case 的 n 都没有太大
: 的情况下。要是 n 非常大的话，那时间差别还是会出来的。