新鲜骨骼电击一

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

游客，您好！
本帖隐藏的内容需要积分高于 190 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

。。。太多follow up
总结 答题不能太快！求大米！

我的想法是，用两个int[24]的辅助数组来存两个字符串中所有字母的出现频率，数组下标对应字母的顺序。
比如acdd，则数组中下标0、2的值为1，下标3的值为2
然后最后比较一下两个辅助数组是不是一样就行了。
楼主你看对吗？

补充内容 (2018-7-4 10:44):
哦，是字符，不是字母，那么就是大小为256的数组。。

StevenXie 发表于 2018-7-5 01:36
统一回复，面试官说O(n)可以降到O(logn), 现在感觉是个陷阱。

这题时间复杂度不会低于O(n)吧？面试官跟你说logn会不会是坑你啊，或者故意试探你让你反驳他并说出不能能logn的理由？

StevenXie 发表于 2018-7-4 11:25
我的思路是用unordered_set把复杂度降到logn.

请问用set的话怎么处理duplicates字符呢？另外这样做如果是把字符串扫一遍，时间复杂度不还是O(n)吗？谢谢！

骨骼电击hhhhh楼主的题目太炫酷

LZ 能给个例子么？时间复杂度如何< O(n)?

FYI 乐扣伞把酒 感谢分享

lentebloem 发表于 2018-7-4 10:40
骨骼电击hhhhh楼主的题目太炫酷

谢谢啦！

houqingniao 发表于 2018-7-4 10:42
LZ 能给个例子么？时间复杂度如何< O(n)?

我的思路是用unordered_set把复杂度降到logn.

感觉这道题就是速度和空间的博弈，即使空间可以达到O（1）同时也会牺牲时间复杂度，而且很有可能达到M*N. 希望各位大神指点！是否可以都达到O(1)

xiaozhi1017 发表于 2018-7-4 10:57
FYI 乐扣伞把酒 感谢分享

确实是原题，不过伞把酒很难hold住follow up