讨论，careercup150 的1.3 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

讨论，careercup150 的1.3

讨论，careercup150 的1.3# JobHunting - 待字闺中

A*g2013-02-18 08:02

1 楼

in place 删除 string里重复的字符。
书上给的算法是3 pointer, O(N^2)
我想，如果先in place quick sort, O(NlgN) 然后用delete duplicates from sorted
array 的方法 O(N)
是不是可以做到O(N+NlgN)呢？

x*62013-02-18 08:02

2 楼

quicksort是要额外空间的

c*t2013-02-18 08:02

3 楼

O(N+NlgN)=O(nLogn),可以是可以，问题是做完以后，岂不是变成另外的string了

sorted

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

: in place 删除 string里重复的字符。
: 书上给的算法是3 pointer, O(N^2)
: 我想，如果先in place quick sort, O(NlgN) 然后用delete duplicates from sorted
: array 的方法 O(N)
: 是不是可以做到O(N+NlgN)呢？