剑指 Offer 51. 数组中的逆序对

难度

• Easy
• Medium
• Hard

思路

使用归并排序。关键点在于归并排序中合并的过程。

我们假设数组的左右两部分已经分别有序： nums_1 = [8, 12, 16, 22, 100] nums_2 = [9, 26, 55, 64, 91] 。

如果我们已经将 8 和 9 加入了合并序列，此时对比 12 和 26 ，显然要将 12 加入合并序列。而 nums_2 中已经有 9 被加入了合并序列，也就是说，26 左边的数字均小于 12 ，但 12 处于数组的左半边，因此与右半边中小于 12 的数字构成了逆序，而与 12 构成逆序的数对数目，正是 nums_2 指针相对起始位置的偏移量。因此，在合并过程中，我们可以很方便地计算逆序数对的数目。

代码

class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        n = len(nums)
        temp = [0 for _ in range(n)]

        def merge(l: int, r: int) -> int:
            if l >= r: return 0
            mid = (l + r) // 2
            ans = merge(l, mid) + merge(mid + 1, r)
            L, R, cur = l, mid + 1, l
            while L <= mid and R <= r:
                if nums[L] <= nums[R]:
                    temp[cur] = nums[L]
                    ans += R - mid - 1
                    L += 1
                else:
                    temp[cur] = nums[R]
                    R += 1
                cur += 1
            while L <= mid:
                temp[cur] = nums[L]
                ans += R - mid - 1
                cur += 1
                L += 1
            while R <= r:
                temp[cur] = nums[R]
                cur += 1
                R += 1
            nums[l:r + 1] = temp[l:r + 1]
            return ans

        return merge(0, n - 1)