另一种算法工作面试

Tra*_*acy 9 algorithm

所以这是一个问题:

假设你有10万个整数,范围从1到100万.请整理整数.时间复杂度应为O(n).

任何分享他或她的想法的人都非常感激.

Fra*_*ank 15

听起来像一个简单的计数排序.

  1. 保留一个大小为100万的阵列的内存
  2. 将所有数组值初始化为0
  3. 循环整数.对于每个整数,我将a [i]递增1.
  4. 通过遍历阵列输出排序的序列并打印每个数字i一次[i]次.

空间是恒定的.运行时为O(n).

  • 还有一件事要补充这个好的答案.对于设置4,如果你想要一个稳定的排序(例如,在绑定的情况下按照预先排序的数组的顺序打印),你应该向后遍历数组. (2认同)