依旧还是面试题,比较麻烦的是,这个排序的关键在于,我们需要时间复杂度为O(n),空间复杂度为O(1).
题目大概是这样的,看了输入输出基本就会明白了:
这里其实主要没做出来是因为我没有很好地理解怎么计算复杂度,尤其是空间复杂度,时间复杂度我勉强记忆成for循环的嵌套还是可以的,但是空间复杂度呢?
这里空间复杂度意味着没有长度为n的数组(但是可以是常量个).
括号里的当时是我没想到的部分,我以为是:一个数组都不能开.
那么问题也就迎刃而解了,使用类似于桶排序的方法即可:
如果您觉得文章不错,可以通过赞助支持我.
如果您不希望打赏,也可以通过关闭广告屏蔽插件的形式帮助网站运作.