Nem*_*emo 16 algorithm
我接受了这个采访:
如果对于i <j,则N [i]> N [j],数字被称为"反向排序".例如,在列表中:3 4 1 6 7 3,反向排序的项目是(3,1)(4,1)(4,3)(6,3)(7,3).
如何在O(nlogn)时间内获得反向排序项的对数.
jle*_*s42 18
可以使用合并排序的修改版本在O(n log n)时间内执行此操作.除法正常,但您可以在合并时计算反转.每次从左侧列表中的项目中选择右侧列表中的项目时,会按左侧列表中剩余项目的数量递增反转计数.因此,在每个级别,反转次数是合并期间发现的反转次数加上每次递归调用所发现的反转次数.
归档时间：
15 年，4 月 前
查看次数：
5427 次
最近记录：
13 年，5 月 前