↓Skip to main content
  1. Posts/

LeetCode-493 翻转对

·1 min·
Table of Contents

LeetCode-493 翻转对 #

Solution 1 #

与经典的统计逆序对数量问题类似, 只不过计数条件略有变化. 重点还是利用归并排序来保证数组的有序性, 把元素间的问题转化成有序数组间的问题. 代码如下:

class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        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):
                while p2 < len(a2) and a1[p1] > 2 * a2[p2]:
                    p2 += 1
                nonlocal ans
                ans += p2
                p1 += 1

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

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