s*x
2 楼
Princeton 大学那本书的经典算法,quicksort on first characters, then second,
then third. 3 way partition in each pass.
then third. 3 way partition in each pass.
c*t
10 楼
想想这个space用的太大 26^26^26...,不太可行
其实也不需要preconstruction, 每个节点的children也不过是26个字母,如果各种字
符,也不过
256字符,用bucket sort, 也是O(1)
所以加入trie的时候, 并不需要太多时间。
【在 c********t 的大作中提到】
: 如果加入trie的时候,需要为每个node排序,那复杂度就差不多了。
: 我的想法,干脆用空间换时间,如果全是小写,干脆preconstruct一个每个节点都分支
: 26个字母的tri, 深度是最长字符串的长度。然后就简单了。O(n) 这个对很大的list
: of Strings应该是很好的优化吧。
: 可行不?
其实也不需要preconstruction, 每个节点的children也不过是26个字母,如果各种字
符,也不过
256字符,用bucket sort, 也是O(1)
所以加入trie的时候, 并不需要太多时间。
【在 c********t 的大作中提到】
: 如果加入trie的时候,需要为每个node排序,那复杂度就差不多了。
: 我的想法,干脆用空间换时间,如果全是小写,干脆preconstruct一个每个节点都分支
: 26个字母的tri, 深度是最长字符串的长度。然后就简单了。O(n) 这个对很大的list
: of Strings应该是很好的优化吧。
: 可行不?
s*x
11 楼
http://algs4.cs.princeton.edu/lectures/51StringSorts.pdf
这里面讲了好几种。 自己看看吧。
【在 c********t 的大作中提到】
: 想想这个space用的太大 26^26^26...,不太可行
: 其实也不需要preconstruction, 每个节点的children也不过是26个字母,如果各种字
: 符,也不过
: 256字符,用bucket sort, 也是O(1)
: 所以加入trie的时候, 并不需要太多时间。
这里面讲了好几种。 自己看看吧。
【在 c********t 的大作中提到】
: 想想这个space用的太大 26^26^26...,不太可行
: 其实也不需要preconstruction, 每个节点的children也不过是26个字母,如果各种字
: 符,也不过
: 256字符,用bucket sort, 也是O(1)
: 所以加入trie的时候, 并不需要太多时间。
c*t
12 楼
Thanks a lot!!!
【在 s**x 的大作中提到】
: http://algs4.cs.princeton.edu/lectures/51StringSorts.pdf
: 这里面讲了好几种。 自己看看吧。
【在 s**x 的大作中提到】
: http://algs4.cs.princeton.edu/lectures/51StringSorts.pdf
: 这里面讲了好几种。 自己看看吧。
相关阅读
上次那个Google NYC的哥们太坑人了问个interview的问题【选择】继续做Intern还是转Temp这个怎么办,郁闷。我惨痛坎坷的OPT经历pre-opt和post-opt能同时申请么?请教几个OPT延期的问题H1b application copy of passport pagesEAD 加急 NSCpost-order?请教一道经典的题-寻找字符串中的最长回文面试归来望指点:怎么通过猎头找工作报一个刚上市L公司的口头offer很接近的offer,在Austin和Phoenix 选哪个好??C#为何念做“see sharp”?不想找工作了A Postdoctoral Position in microfabrication (repost)onsite结束到现在已是第二个星期发现一个问题:晚上看算法难题,睡眠质量很差。