我有一个任意顺序的唯一整数数组(例如 val[i]
),我想填充另一个数组(ord[i]
)与整数的排序索引。换句话说,val[ord[i]]
按照 i
递增的顺序排列。
现在,我只是用 0, ..., N 填充 ord
,然后根据值数组对其进行排序,但我想知道我们是否可以更有效地处理 code>ord
开始时未填充。这更多是出于好奇而提出的问题;我真的不关心必须预填充列表然后对其进行排序的额外开销(它很小,我使用插入排序)。这可能是一个答案很明显的愚蠢问题,但我在网上找不到任何东西。
最佳答案
就时间复杂度而言,没有比排序更快的方法了。如果有,那么您可以使用它来更快地排序:生成索引,然后使用它们对原始数组重新排序以使其按排序顺序排列。这种重新排序将花费线性时间,因此总体而言您将拥有更快的排序算法,从而产生矛盾。
关于algorithm - 确定数字列表的顺序(可能不需要排序),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2777371/