给定 [n] 的未排序排列,我想通过从左到右迭代来收集数字,以便对预排列 (1...n) 进行排序。
为了实现这个目标,我必须进行多少次迭代?
例如:
给定 '3, 7, 4, 2, 10, 8, 9, 1, 6, 5' - 迭代次数为 6。
在第一次迭代中,我将收集数字 1
在第二次迭代中,我将收集数字 2
在第三次迭代中,我将收集数字 3、4、5
在第四次迭代中,我将收集数字 6
在第五次迭代中,我将收集数字 7、8、9
在第六次迭代中,我将收集数字 10
我构建了一个天真的代码,用 O(n^2) 完成任务,但我需要它更高效,所以我认为我在这里缺少一个技巧。
有什么建议吗?
最佳答案
反转排列,然后计算两个连续数字递减加一的次数。
def iterations(perm):
invperm = [None] * len(perm)
for i in range(len(perm)): # yes, we could use enumerate
invperm[perm[i] - 1] = i
count = 1
for i in range(1, len(perm)):
count += invperm[i - 1] > invperm[i]
return count
解释:
Given : 3, 7, 4, 2, 10, 8, 9, 1, 6, 5 x : 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
Index of x in the given array : |8, |4, |1, 3, 10, |9, |2, 6, 7, |5
如果索引乱序,则必须重新开始。因此,如果您计算 |
,那么您就知道需要的迭代次数。
关于algorithm - 有效地排序排列,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/27582089/