我们能给出空间复杂度为O(n)的n个元素的计数排序算法吗？

Question

我今天有一个期中考试，其中一个算法题是“我们能不能让计算排序O(n)的空间复杂度为n个元素”。实际上，我找不到任何解决这些问题的方法。有没有人知道任何算法或数据结构。我想知道答案并思考一下。非常感谢。

Answer 1

如果我们在计数排序中使用数组进行计数，那么它需要的空间等于最大键值和最小键值之间的差值。我们可以使用哈希表，然后我们可以将空间复杂度降低到相对于输入元素数量的线性。但在这种情况下，隐藏常量可能太大，性能可能会下降。