每个元素出现次数至少为n/1000的数组能否实现O(n)时间排序？

这个问题的核心突破口在于题目给出的元素出现频率下限——每个元素至少出现n/1000次，咱们可以基于这个条件设计出线性时间的排序方案，具体思路如下：

关键前提推导 #

首先计算数组中不同元素的最大数量：假设存在k个不同元素，每个至少出现n/1000次，那么总元素数n ≥ k*(n/1000)，两边约掉n（n>0）就能得到k ≤ 1000。也就是说，数组里的不同元素最多只有1000种，这是个固定的常数！

具体算法步骤 #

• 第一步：统计元素频率
  遍历整个数组，用哈希表（或者如果元素是整数类型，也可以用数组）记录每个元素的出现次数。这一步的时间复杂度是O(n)，因为每个元素只需要遍历一次，哈希表的插入/查询操作平均时间是O(1)。
• 第二步：排序不同元素
  把哈希表中所有的键（也就是不同的元素）提取出来，进行排序。因为最多只有1000个元素，这一步的时间复杂度是O(k log k)，而k=1000是常数，所以这一步的时间可以看作是O(1)（和n的规模无关）。
• 第三步：重构排序后的数组
  遍历排序好的不同元素，按照每个元素的出现次数，将重复的元素依次写入结果数组。比如元素x出现了m次，就连续写m个x。这一步的总操作次数是n，所以时间复杂度也是O(n)。

复杂度分析 #

把三步的时间加起来：O(n) + O(1) + O(n) = O(n)，完全满足题目要求的线性时间复杂度。

补充说明 #

这种思路本质上是计数排序/桶排序的变种，区别在于普通计数排序需要知道元素的取值范围，而这里我们利用频率条件先限制了不同元素的数量，再结合哈希表统计，就不需要提前知道取值范围了。如果没有这个频率条件，基于比较的排序算法的下界是O(n log n)，但因为这里元素种类数是常数，所以可以突破这个下界。

内容的提问来源于stack exchange，提问作者Julian Shaer