请教一道国内面试算法题，很短，没做出来

empy · 2017-10-29 06:49:44

yanshuo619 发表于 2017-10-29 06:40
要求只是返回长度所以并不需要知道具体是哪个没出现。有了input长度直接可以算出来每个长度应该有多少组合 ...

set长度最高为log4(n)，所以遍历每个元素时遍历log4(n)次，总的时间复杂度为nlog4(n)。

chowhound · 2017-10-29 06:58:46

empy 发表于 2017-10-29 06:49
set长度最高为log4(n)，所以遍历每个元素时遍历log4(n)次，总的时间复杂度为nlog4(n)。

每个元素只是跟前一个状态合起来仍set里，为啥会需要遍历呢

empy · 2017-10-29 07:10:04

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

EddieStallworth · 2017-10-29 07:13:43

k1938slll 发表于 2017-10-29 05:03
好难？！ Google的题吗

百度的字数字数

EddieStallworth · 2017-10-29 07:15:09

fangdanzai 发表于 2017-10-29 05:10
先把所有可能的组合存在hash里然后用长度从1到length遍历？

不能暴力解啊那还有啥意思了..

EddieStallworth · 2017-10-29 07:16:21

yanshuo619 发表于 2017-10-29 06:40
要求只是返回长度所以并不需要知道具体是哪个没出现。有了input长度直接可以算出来每个长度应该有多少组合 ...

面试完了以后我又想了一下应该这样做是可行的

无量塔 · 2017-10-29 07:40:08

empy 发表于 2017-10-29 07:10
时间复杂度 nlog4(n)

补充内容 (2017-10-29 07:13):

substr也是需要时间的

mmymichael · 2017-10-29 07:43:10

twitter OA questions. i have seen this question last year

empy · 2017-10-29 07:58:40

无量塔发表于 2017-10-29 07:40
substr也是需要时间的

即使substr的时间复杂度是O(n),总的复杂度也不过是多乘一个log4(n)

magicsets · 2017-10-29 16:40:40

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式