++wythern++

X presents Y for a better Z

【笔记】逆序数的求法

做个笔记!
【参考】http://blog.csdn.net/dlengong/article/details/7594919

3种思路:
1. 冒泡法统计交换次数。 O(N*N)
2. MergeSort同时统计。 O(NlogN)
3. 用binary index tree!。 O(NlogN),其实是基于IndexSort,然后用BinIdxTree求和。
   BIT适用的场景是:
   对于某个序列a0, a1, a2, ..., aN.
   BITsum(0, m) [0 <= m <= N] == sum(a0, a1, ..., am).
   和普通的sum不同点在于,当ai发生变化的时候,BIT支持在logN时间内重新算出sum值。
   所以这条求逆序的方式就是indexSort找到当前max value对应的idx, 然后a(idx) = 1,然后BITsum(0, idx)看看前面有多少1,就是当前value的逆序数K, sum(K)就得到了整个序列的逆序数。

posted on 2016-02-14 21:27 wythern 阅读(177) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理