请教一个Leetcode上的算法题

zengxinzhy 发表于 2013-3-5 05:06
楼主的想法确实是O(n)的复杂度，因为：
扫描数据，放入hashset中：O(n)
遍历hashset时，每个元素最多被到 ...

Sorry, 开始的时候把楼主的遍历方法理解错了，把关于m的分析跳过

zengxinzhy 发表于 2013-3-5 17:45
遍历的时候是可以这么做，但为位图开辟一片空间以后首先是需要初始化的，把位图中的所有数据都设为0，这一 ...

hash也是要初始化的，hash的大小和希望获得的冲突的概率以及数据有关。
再者题目无非是想考查如何稀疏访问数据，而所给假设不足，本身就没有完美答案

好困想睡觉 发表于 2013-3-5 06:31
hash也是要初始化的，hash的大小和希望获得的冲突的概率以及数据有关。
再者题目无非是想考查如何稀疏访 ...

是的。
Hash的大小一般会设为n的两倍左右，平均情况下复杂度为O(n)，但是在最坏最坏很倒霉的情况下复杂度会达到O(n^2)
Bitmap的时间和空间复杂度都为O(k)，但是能保证每次运行复杂度都这么高。
就看trade off怎么选择吧。
一般看算法题的时候，我都是默认复杂度的要求是平均复杂度，而不是最坏时候的复杂度，不然quick sort之类的一大堆算法都没法用了

谢谢各位了，学到很多~ Delete Hash的确不是一个好办法，我后来想到开个n大小的数组记录每个元素是否被visited过，如果visited了就当作被删除掉好了。至于初始化时候的insert ... 偶们就当做是平均复杂度吧……

我觉得O(n) 是不合适的。
原因是：“向上”“向下”的炸找，并不能算做O(1)的，因为并不知道，“向上”“向下”几个。
但是这个怎么衡量，我也没有思路，请教大拿。

可以是O(n)的，思路和你的差不多。
只不过，每次只需要考虑上一个，和 下一个。
代码：https://gist.github.com/sing1ee/5105469
perl的，不过很好懂。

sing1ee 发表于 2013-3-7 11:52
可以是O(n)的，思路和你的差不多。
只不过，每次只需要考虑上一个，和 下一个。
代码：https://gist.gith ...

懂啦，谢谢~这个比我那个思路清晰~

大神 能否简单说下解题思路  在网上看这个的解法  各种看不懂  55