c++ - 对这 n^2 个数字进行排序的最快方法是什么？

Question

给定一个数字“n”，我想返回一个包含 n^2 个数字的排序数组，其中包含 k1*k2 的所有值，其中 k1 和 k2 的范围可以从 1 到 n。

例如对于 n=2 它将返回:{1,2,2,4}。(数字基本上是 1*1,1*2,2*1,2*2)。

对于 n=3，它将返回:{1,2,2,3,3,4,6,6,9}。

(数字是:1*1、2*1、1*2、2*2、3*1、1*3、3*2、2*3、3*3)

我尝试使用 c++ 标准库中的排序函数，但我想知道是否可以进一步优化它。

Answer 1

嗯，首先，你得到 n^2 个条目，其中最大的是 n^2，并且在可能的值范围中，只有很小的一个值的数量用于较大的 n。因此，我建议采用计数方法:

1. 用零初始化大小为 n^2 的数组 counts[]。
2. 遍历值数组 values[]，然后执行 counts[values[i]-1]++。
3. 通过遍历 counts 数组重新初始化 values 数组，将尽可能多的 i+1 值放入 values 数组作为 counts[i] 给你。

就是这样。它是 O(n^2)，因此您很难找到性能更高的解决方案。