给定一个长度为 N 的数组。它可以包含从 1 到 N^2(N 的平方)范围内的值,包括两端值,值是整数。是否可以在 O(N) 时间内对这个数组进行排序?如果可能怎么办?
编辑:这不是作业。
最佳答案
以N为底写出每个整数,即每个x都可以表示为(x1, x2),其中x = 1 + x1 + x2*N。现在您可以使用 counting sort 对它进行两次排序,一次在 x1 上,一次在 x2 上,生成排序数组。
编辑:正如下面提到的其他人,像这样分别对每个“数字”进行排序称为 radix sort .使用计数排序对每个数字进行排序需要 O(N) 时间和 O(N) 空间(在这种特殊情况下)。由于我们恰好重复两次,因此总运行时间为 O(N)。
关于algorithm - 长度为 N 的数组可以包含值 1,2,3 ... N^2。是否可以在 O(n) 时间内排序?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4238460/