algorithm - 另一种算法求职面试

Question

问题来了:

Suppose you have 100 thousand integers which ranges from 1 to 1 million. Please sort out the integers. The time complexity should be O(n).

任何分享他或她的想法的人都会受到赞赏。

Answer 1

听起来像是一种简单的计数排序。

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

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