题目描述：

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.

题目大意：

给定数组nums，定义所有满足i < j 并且nums[i] > 2 * nums[j]的数对(i, j)为“重要的逆序对”（important reverse pair）。返回其个数。

注意：

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

解题思路：

树状数组 （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操作

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)
            ft.add(dmap[n], 1)
        return ans

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

    def add(self, x, val):
        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

 

本文链接：http://bookshadow.com/weblog/2017/02/12/leetcode-reverse-pairs/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码