剑指offer：数组中的逆序对

题目描述
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007
输入描述:
题目保证输入的数组中没有的相同的数字

数据范围：

    对于%50的数据,size<=10^4

    对于%75的数据,size<=10^5

    对于%100的数据,size<=2*10^5

示例1
输入 1,2,3,4,5,6,7,0
输出 7

# -*- coding: utf-8 -*-
# @Time         : 2019-07-12 11:39
# @Author       : Jayce Wong
# @ProjectName  : job
# @FileName     : inversePairs.py
# @Blog         : https://blog.51cto.com/jayce1111
# @Github       : https://github.com/SysuJayce

class Solution:
    """
    要计算数组中的逆序对的对数，那么最直观的做法就是遍历整个数组，将当前元素和后续的所有元素进行
    比较，然后累计有多少逆序对。

    另一种解法就是基于归并排序的解法。
    上述的解法的最大缺陷在于每个数字都要跟后续的所有数字进行比较，导致时间复杂度为O(n^2)。
    如果可以避免这么多次比较，就可以提高效率。
    效仿归并排序，我们先将一个数组不断对半分裂，先得到多个长度为1的数组，然后每两个相邻数组进行比较
    然后归并。
    **之所以要进行归并(将这两个相邻数组合并后排序)是因为如果不排序的话，在下一轮的比较的时候会出现
    重复计数的情况**
    由于进行了排序，在下一轮归并的时候只需要将两个数组的最大值进行比较，如果左边的数组的最大值大于
    右边数组的最大值，那么说明右边整个数组都可以跟左边数组的最大值组成逆序对，因此跳过左边数组最大
    值和右边剩余元素的比较。
    这种解法其实就是**降序的归并排序**。
    """

    def InversePairs(self, data):
        def split(start, end):
            # 先将整个数组对半分裂成若干个长度为1的数组
            if start < end:  # start < end，说明长度大于1，继续分裂
                mid = (start + end) >> 1
                split(start, mid)
                split(mid + 1, end)
                # 分裂完成后，对两个相邻数组进行归并
                # 两个数组的下标分别为[start, mid], [mid + 1, end]
                merge(start, mid, end)

        def merge(start, mid, end):
            # 由于我们这里的count是InversePairs()里的局部变量，
            # 所以用nonlocal关键字而非global
            nonlocal count
            # 由于是进行降序归并，因此从两个数组的末尾开始归并
            p1 = mid
            p2 = end
            while p1 >= start and p2 > mid:
                # 如果左边大于右边，说明组成了一个逆序对，
                # 计数器count增加数值为右边数组的剩余元素个数
                if data[p1] > data[p2]:
                    # count += end - p2 + 1
                    count += p2 - mid
                    # data_copy用于存储归并后的结果
                    data_copy.append(data[p1])
                    p1 -= 1
                else:
                    data_copy.append(data[p2])
                    p2 -= 1
            # 将左右数组剩余的元素加入data_copy中，由于是有其中一个数组完全为空了，所以事实上
            # 只将其中一个数组的元素加入data_copy中，而由于我们是利用递归实现的，这个数组也早
            # 已有序，因此归并后的结果data_copy是有序的
            for p in range(p1, start - 1, -1):
                data_copy.append(data[p])
            for p in range(p2, mid, -1):
                data_copy.append(data[p])
            # 将归并结果赋值到原数组中，注意这里赋值的顺序，我们要保证从小到大。
            while data_copy:
                data[start] = data_copy.pop(-1)
                start += 1

        if not data:
            return 0

        count = 0  # 用于统计逆序对的对数
        data_copy = []  # 辅助数组，用于存储两个相邻数组归并的临时结果
        split(0, len(data) - 1)
        return count % 1000000007

def main():
    solution = Solution()
    data = [364, 637, 341, 406, 747, 995, 234, 971, 571, 219, 993, 407, 416,
            366, 315, 301, 601, 650, 418, 355, 460, 505, 360, 965, 516, 648,
            727, 667, 465, 849, 455, 181, 486, 149, 588, 233, 144, 174, 557, 67,
            746, 550, 474, 162, 268, 142, 463, 221, 882, 576, 604, 739, 288,
            569, 256, 936, 275, 401, 497, 82, 935, 983, 583, 523, 697, 478, 147,
            795, 380, 973, 958, 115, 773, 870, 259, 655, 446, 863, 735, 784, 3,
            671, 433, 630, 425, 930, 64, 266, 235, 187, 284, 665, 874, 80, 45,
            848, 38, 811, 267, 575]
    # data = [1,2,3,4,5,6,7,0]
    print(solution.InversePairs(data))

if __name__ == '__main__':
    main()