arrays - 是否有 O(n) 算法为正整数数组生成无前缀数组？

Question

对于数组[4,3,5,1,2]，我们称4的前缀为NULL，4的无前缀为0； 3的prefix是[4]，3的prefix-less是0，因为prefix中没有一个小于3； 5的前缀是[4,3]，5的无前缀是2，因为4和3都小于5； 1的prefix是[4,3,5]，1的prefix-less是0，因为prefix中没有一个小于1； 2的前缀是[4,3,5,1]，2的无前缀是1，因为只有1小于2

所以对于数组 [4, 3, 5, 1, 2]，我们得到 [0,0, 2,0,1] 的无前缀数组，我们可以得到一个 O(n) 算法来获得无前缀数组吗？

Answer 1

它不能在 O(n) 中完成，原因与 comparison sort 相同需要 O(n log n) 比较。可能的无前缀数组的数量是 n!，因此您至少需要 log2(n!) 位信息来识别正确的无前缀数组。 log2(n!) 是 O(n log n)，由 Stirling's approximation .