剑指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()

另外有需要云服务器可以了解下创新互联cdcxhl.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。