有一个数组A[1, ..., n] ，它知道每个 1 <= l <= n然后 A[l] in {1,2,...,n^5} .
我怎样才能找到一个在 O(n) 中对它进行排序的算法？
最佳答案
想象在 Base-n 系统中表示 A[i] 中的值。然后每个数字变成一个五位数的 n 进制数，这意味着您可以使用 Radix Sort 的五个应用程序对整个数组进行排序。 ，“基数”为 n。
按如下方式计算数字 k 中每个“数字”x 的值:
dx = (k/(n x)) % n
其中/表示整数除法。
关于algorithm - 用 O(n) 中的值范围对数组进行排序，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/44119945/