FB电面

第一题 sort 后space不就变成O(n) 了吗？

nogiveup 发表于 2021-08-14 08:45:54
第一题 sort 后space不就变成O(n) 了吗？

Sort为什么是On space呢？

TDsomething 发表于 2021-8-14 17:51
Sort为什么是On space呢？

我用的是python， 通常sort() 就是时间复杂度O(nlogn) 空间复杂度O(n). 难道我记错了？？？

nogiveup 发表于 2021-08-14 19:57:29
我用的是python， 通常sort() 就是时间复杂度O(nlogn) 空间复杂度O(n). 难道我记错了？？？

不太清楚Python sort()的complexity，不过in place 的sorting不是O1吗？

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

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

nogiveup 发表于 2021-8-15 14:22
好像别的语言有的用in-place sort像quicksort之类的就是O(1)啦，Python的sort() 用的是Timsort()就是O(n) ...

我觉得没必要纠结这个，知道sort是NlogN time就够了。

hfpt2020 发表于 2021-8-14 08:32
1^2^3=0

多谢指正

请问一下lz第二题有被问到要求O(1) space吗，还是说只要能答出来用hashmap存copy的解法就行？

p6152859 发表于 2021-08-29 15:35:04
请问一下lz第二题有被问到要求O(1) space吗，还是说只要能答出来用hashmap存copy的解法就行？

并没有，用的dfs On