看到一个问题，大家讨论一下 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

看到一个问题，大家讨论一下

看到一个问题，大家讨论一下# JobHunting - 待字闺中

h*d2014-05-14 07:05

1 楼

given a string - tuTutuuti, print it as output: t3u4T1i1 in O(n) time
without using any extra spaces and maps/etc other data structures
O(n) time and O(1) time? use counting sort?

q*m2014-05-14 07:05

2 楼

constant space 是O(1)space

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

: given a string - tuTutuuti, print it as output: t3u4T1i1 in O(n) time
: without using any extra spaces and maps/etc other data structures
: O(n) time and O(1) time? use counting sort?

d*k2014-05-14 07:05

3 楼

怀疑究竟有没有这样的答案。

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

: given a string - tuTutuuti, print it as output: t3u4T1i1 in O(n) time
: without using any extra spaces and maps/etc other data structures
: O(n) time and O(1) time? use counting sort?

p*p2014-05-14 07:05

4 楼

without using any extra spaces应该是不可能的，不然abc -> a1b1c1怎么办
O(1)可行，假设共n个不同字符，把缓冲区扩到2n然后从后往前走

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

: given a string - tuTutuuti, print it as output: t3u4T1i1 in O(n) time
: without using any extra spaces and maps/etc other data structures
: O(n) time and O(1) time? use counting sort?