493. Reverse Pairs

描述

Given an array nums, we call (i, j) an important reverse pair if i < j and nums[i] > 2*nums[j].

You need to return the number of important reverse pairs in the given array.

Example1:

Input: [1,3,2,3,1]
Output: 2

Example2:

Input: [2,4,3,5,1]
Output: 3

解法

使用归并排序，合并之前先统计满足条件的 important reverse pair 的数量。

class Solution:
    def reversePairs(self, nums):
        self.pairs = 0

        def merge_sort(nums):
            if len(nums) < 2:
                return nums

            mid = len(nums) // 2
            left = merge_sort(nums[:mid])
            right = merge_sort(nums[mid:])
            return merge(left, right)

        def merge(left, right):
            j = 0
            for num in left:
                while j < len(right) and num > 2 * right[j]:
                    j += 1
                self.pairs += j
            return sorted(left + right)

        merge_sort(nums)
        return self.pairs

核心是 merge 中统计的过程，例如 left = [4, 9, 16, 32], right = [1, 2, 3, 4]。对应的 j 的值分别为 1, 4, 4, 4。总计为 13。

小结

归并排序思想的使用，还有一个常见的场景是统计逆序对的数量。

引用

General principles behind problems similar to "Reverse Pairs"