↓Skip to main content
  1. Posts/

LeetCode-LCR170 交易逆序对的总数

·1 min·
Table of Contents

LeetCode-LCR170 交易逆序对的总数 #

Solution 1 #

非常经典的问题: 逆序对计数. 暴力统计的复杂度是 $O(n^2)$ , 效率不够高. 对于某个元素, 有没有办法能一次性统计多个包含它的逆序对呢? 这要求数组的某些部分是有序的, 我们用归并排序来保证这一点. 事实上, 在归并排序的合并过程中, 前后两部分都保持了有序. 此时, 每个加入排序后数组的前半部分的元素, 都可以一次性统计后半部分的元素和它构成的逆序对数量. 至于前半部分内部的, 在之前的递归部分中已经被统计过了. 代码如下:

class Solution:
    ans = 0
    def reversePairs(self, record: List[int]) -> int:
        self.ans = 0

        def merge_sort(a):
            n = len(a)
            if n <= 1:
                return a
            a1, a2 = a[:n // 2], a[n // 2:]
            a1 = merge_sort(a1)
            a2 = merge_sort(a2)
            res = []
            p1, p2 = 0, 0

            while p1 < len(a1) and p2 < len(a2):
                if a1[p1] <= a2[p2]: 
                    self.ans += p2
                    res.append(a1[p1])
                    p1 += 1
                else:
                    res.append(a2[p2])
                    p2 += 1

            while p1 < len(a1): 
                self.ans += len(a2)
                res.append(a1[p1])
                p1 += 1
                
            while p2 < len(a2):
                res.append(a2[p2])
                p2 += 1
            
            return res
        merge_sort(record)
        return self.ans