使用树状数组来快速计算逆序对数、第K大/小的数

作者: qwq 分类: 算法 发布时间: 2017-12-19 20:51

计算逆序对数:

对于一个数列a[n],需要计算第k位的数有多少个逆序对数。

就是要计算在第k位之后,有多少数a[i], i>k && a[i]<a[k] 。

方法是逆序计算。

类似于桶排序,新开一个数组b[max{a[i]}],数组的大小要大于a数组中最大值的大小。

对a数组进行从后往前遍历,将b[a[i]]++。

对于要求的第k位数的逆序对,就是要求b[0]~b[a[k]]这个区间的和是多少。

可以很方便的用树状数组来计算。

 

计算第K大/小的数也是同理,加上一个二分搜索就可以了。

时间复杂度是nlognlogn,不算低。

还有一个复杂度为LogN的算法。

待更新

 

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注