【第三轮】6.16-6.22 CareerCup 1.5

wilbert 发表于 2014-6-18 02:51
【解题思路】
compare the current character with the previous one, if equals, cnt++, otherwise, appe ...

谢谢帮我review！我的疑问是比如aaaaaaa，这样result的string就会很小，空间复杂度的上限是O(N)吧，下限是O(1)。

asdw3276 发表于 2014-6-18 20:17
谢谢帮我review！我的疑问是比如aaaaaaa，这样result的string就会很小，空间复杂度的上限是O(N)吧，下限 ...

没错，空间复杂度和时间复杂度一样，用的都是high order term，所以就是O(N)了

wilbert 发表于 2014-6-18 22:34
没错，空间复杂度和时间复杂度一样，用的都是high order term，所以就是O(N)了

时间复杂度应该不是取上限。反例是快排是O(n lg n)的时间复杂度，而不是O(N^2)的时间复杂度。
ps你的follow up question很有意思。如果采用一个有限自动机循环读取压缩后的字符串，是可以还原原字符串的。

asdw3276 发表于 2014-6-19 00:58
时间复杂度应该不是取上限。反例是快排是O(n lg n)的时间复杂度，而不是O(N^2)的时间复杂度。
ps你的fol ...

快排的 nlg(n) 复杂度取的是平均时间复杂度。
'aaaaaaaaaaaaaaaaaaa'之类的test case显然是极端情况..不可取

小柯西 发表于 2014-6-19 01:03
快排的 nlg(n) 复杂度取的是平均时间复杂度。
'aaaaaaaaaaaaaaaaaaa'之类的test case显然是极端情况..不 ...

你没理解我的意思。
我在23楼讨论的是：时间复杂度是否应该取high order term，跟此题目无关。我的观点就是取平均时间复杂度。

asdw3276 发表于 2014-6-19 01:33
你没理解我的意思。
我在23楼讨论的是：时间复杂度是否应该取high order term，跟此题目无关。我的观点 ...

- -我的回复也不光是针对你23楼的讨论的。。
那既然是取平均复杂度。。再回到你这道题的算法，我也不觉得你光用极端情况就能证明你算法的平均空间复杂度可以达到O(1)

小柯西 发表于 2014-6-19 01:44
- -我的回复也不光是针对你23楼的讨论的。。
那既然是取平均复杂度。。再回到你这道题的算法，我也不觉 ...

这道题空间复杂度确实不是O(1)，这个没错。。。

【解题思路】
  Save the first character. Iterate and compare next character, increment count
  Concatenate character and count to a new string, return it if the length is shorter
【时间复杂度】
  O(N)
【空间复杂度】
  O(N)
【gist link】https://gist.github.com/hilda8519/70b9e1c9aecf67189c27
基本上就是书上的【test case】
m1y1d1o1g1i1s1m1a1o1t1o1u1
mydogismaotou

asdw3276 发表于 2014-6-19 00:58
时间复杂度应该不是取上限。反例是快排是O(n lg n)的时间复杂度，而不是O(N^2)的时间复杂度。
ps你的fol ...

我举个例子吧， a1和111个a都能compress出a111，我们现成的这种算法是无法还原的。

【解题思路】
use StringBuffer. Traverse the String to count and compress. Check the length of the compressed String to determine the return value.
【时间复杂度】
O(n)
【空间复杂度】
O(n)
【gist link】
https://gist.github.com/jyhjuzi/0cc707143aa257ea9288