跳转至

树状数组求逆序对

image-20190928120135926

1、什么是逆序对

如果 i < j 并且 A[i]>A[j]

2、如何求解一共有多少逆序对

逆序对的个数,就等于对每个元素来讲,相当于将所有元素之前大于当前元素的数量加起来,也相当于是求解当前元素之后有多少元素小于当前元素

3、树状数组实现

树状数组能够进行简便的更新查询操作,因此,使用树状数组保存当前元素之前有多少元素大于当前元素

假设原数组为:
1 2 3 4 5

当前数组为:
5 4 3 2 1

首先要确定每个元素以前在数组中的位置:
5-4
4-3
3-2
2-1
1-0

数组初始化:
[0,0,0,0,0]
1、首先是第一个元素5,以前的位置为4,更新数组对应更新+1
    [0,0,0,0,1]
    判断当前元素之前有多少小于当前元素的
    当前判断的数量 - 该位置之前的所有元素数量
    1 - 1 =0
2、然后是元素4,以前的位置应该为3,更新数组,对应更新+1
    [0,0,0,1,1]
    2 - 1 = 1
    已经判断了2个元素,但是小于当前元素的只有1个,因此逆序对为1
3、 然后是元素3,以前的位置应该为2,更新数组,对应更新+1
    [0,0,1,1,1]
    3 - 1 = 2
    已经判断了3个元素,但是小于当前元素的只有1个,因此逆序对为2

依次类推
上面的查询更新操作使用树状数组实现即可

下面的求解逆序对,实际上可以通过求解当前元素后面有多少小于当前值的数字

代码实现:

from typing import List


class BinaryIndexTree:
    def __init__(self, num):
        """
        :type nums: List[int]
        """

        self.buff = [0] * (num + 1)

    def update(self, i, val):
        """
        :type i: int
        :type val: int
        :rtype: void
        """
        index = i + 1
        while index < len(self.buff):
            self.buff[index] += val
            index += index & (-index)

    def getSum(self, index):
        index += 1
        res = 0
        while index > 0:
            res += self.buff[index]
            index -= index & (-index)
        return res


class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        mapping = {val: key for key, val in enumerate(sorted(set(nums)))}
        bit = BinaryIndexTree(len(mapping))

        ans = 0

        for index, num in enumerate(reversed(nums)):
            bit.update(mapping[num], 1)
            ans += bit.getSum(mapping[num] - 1)

        return ans


s = Solution()
print(s.countSmaller([5, 2, 6, 1]))
print(s.countSmaller([5, 2, 6, 5, 1, 1]))
4
10
[5, 2, 6, 1]

数字    逆序对
1   ->  0
6   ->  1
2   ->  1
5   ->  2

总逆序对为:4
[5, 2, 6, 5, 1, 1]

数字    逆序对
1   ->  0
1   ->  0
5   ->  2
6   ->  3
2   ->  2
5   ->  3

总逆序对为:10