数组中的逆序对

数组中的逆序对_牛客题霸_牛客网

问题简述

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P mod 1000000007

思路：归并排序

• 利用归并排序中的合并操作，统计逆序对数量；

  • 以合并 a1 = [1, 7, 8]、a2 = [2, 5, 6] 这两个子数组为例：

    tmp = []  # 临时容器保存已经有序的部分
    l, r 分别指向 两个子数组 的开始位置，依次对比 a[l] 和 a[r]，将较小的数保存在 tmp 中；
    
    当进行到 tmp = [1], a1 = [7, 8], a2 = [2, 5, 6] 时，有 7 > 2，可以得到 (7, 2) 和 (8, 2) 两个逆序对；
    即每当遇到 a[l] > a[r] 时，可以得到 m - l + 1 个逆序对；其中 m 为左子数组的长度

Python 写法1（推荐）

class Solution:
    def InversePairs(self , data: List[int]) -> int:
        
        def merge(a, lo, hi):
            if lo >= hi: return 0
            
            ret = 0
            m = (lo + hi) // 2
            ret += merge(a, lo, m)  # 左子数组能产生的逆序对数量
            ret += merge(a, m + 1, hi)  # 右子数组能产生的逆序对数量
            
            tmp = []  # 临时容器保存已经有序的部分
            l, r = lo, m + 1
            while l <= m and r <= hi:
                if a[l] <= a[r]:
                    tmp.append(a[l])
                    l += 1
                else:  # a[l] > a[r]
                    ret += m - l + 1  # 当前位置能产生的逆序对
                    tmp.append(a[r])
                    r += 1
            
            tmp += a[l:m + 1] or a[r:hi + 1]  # 拼接剩余部分，此时不会产生逆序对
            a[lo:hi + 1] = tmp
            return ret
        
        ret = merge(data, 0, len(data) - 1)
        # print(data)
        return ret % 1000000007

Python 写法2

class Solution:
    def InversePairs(self , data: List[int]) -> int:
        
        def merge(a, lo, hi):
            if lo >= hi: return 0
            
            ret = 0
            m = (lo + hi) // 2
            ret += merge(a, lo, m)
            ret += merge(a, m + 1, hi)
            
            tmp = [0] * (hi - lo + 1)
            l, r = lo, m + 1
            for i in range(len(tmp)):

                # 写法 1
                if l <= m and r <= hi:
                    if a[l] <= a[r]:
                        tmp[i] = a[l]
                        l += 1
                    else:
                        ret += m - l + 1
                        tmp[i] = a[r]
                        r += 1
                elif l == m + 1:
                    tmp[i] = a[r]
                    r += 1
                else:  # r == hi + 1
                    tmp[i] = a[l]
                    l += 1
                
                # 写法 2
                # if l == m + 1:
                #     tmp[i] = a[r]
                #     r += 1
                # elif r == hi + 1 or a[l] <= a[r]:
                #     tmp[i] = a[l]
                #     l += 1
                # else:  # a[l] > a[r]
                #     ret += m - l + 1
                #     tmp[i] = a[r]
                #     r += 1
                    
            a[lo: hi + 1] = tmp
            return ret
        
        ret = merge(data, 0, len(data) - 1)
        # print(data)
        return ret % 1000000007