## 题目描述：

LeetCode 493. Reverse Pairs

Given an array `nums`, we call `(i, j)` an important reverse pair if `i < j` and `nums[i] > 2*nums[j]`.

You need to return the number of important reverse pairs in the given array.

Example1:

```Input: [1,3,2,3,1]
Output: 2
```

Example2:

```Input: [2,4,3,5,1]
Output: 3
```

Note:

1. The length of the given array will not exceed `50,000`.
2. All the numbers in the input array are in the range of 32-bit integer.

## 题目大意：

1. 数组长度不超过50,000。
2. 所有数字在32位整数范围内。

## 解题思路：

```1. 将原数组所有元素乘以2后得到数组nums2

2. 将nums与nums2合并后进行离散化处理（排序+去重），从实数范围映射到 [1, len(set(nums + nums2))]，记得到的映射为dmap

3. 从右向左遍历nums2，记当前数字为n，统计(0, dmap[n / 2])的区间和，然后对树状数组的dmap[n]位置执行+1操作```

## Python代码：

``````class Solution(object):
def reversePairs(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
nums2 = [n * 2 for n in nums]
dmap = { v : k + 1 for k, v in enumerate(sorted(set(nums + nums2))) }
ft = FenwickTree(len(dmap))
ans = 0
for n in nums2[::-1]:
ans += ft.sum(dmap[n / 2] - 1)
return ans

class FenwickTree(object):
def __init__(self, n):
self.n = n
self.sums = [0] * (n + 1)

while x <= self.n:
self.sums[x] += val
x += self.lowbit(x)

def lowbit(self, x):
return x & -x

def sum(self, x):
res = 0
while x > 0:
res += self.sums[x]
x -= self.lowbit(x)
return res
``````

Pingbacks已关闭。