【题目描述】
For an array A, if i < j, and A [i] > A [j], called (A [i], A [j]) is a reverse pair.
return total of reverse pairs in A.
在数组中的两个数字如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。给你一个数组，求出这个数组中逆序对的总数。
概括：如果a[i] > a[j] 且 i < j， a[i] 和 a[j] 构成一个逆序对。
【题目链接】
www.lintcode.com/en/problem/reverse-pairs/
【题目解析】
可以利用树状数组 （Binary Indexed Tree / Fenwick Tree）
1. 将原数组所有元素乘以2后得到数组nums2
2. 将nums与nums2合并后进行离散化处理（排序+去重），从实数范围映射到 [1, len(set(nums + nums2))]，记得到的映射为dmap
3. 从右向左遍历nums2，记当前数字为n，统计(0, dmap[n / 2])的区间和，然后对树状数组的dmap[n]位置执行+1操作
【参考答案】
网友评论