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

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

问题

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

示例 1:

1
2
输入: [7,5,6,4]
输出: 5

限制：

1
0 <= 数组长度 <= 50000

分析

涉及数组元素两两比较，想归并排序；结合归并排序过程，求解问题。

复杂度：$T(n) = O(nlogn); S(n) = O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        def merge(nums, left, mid, right):
            temp = nums.copy()
            i, j = left, mid + 1
            k = i
            while i <= mid and j <= right:
                if temp[i] <= temp[j]:
                    nums[k] = temp[i]
                    i += 1
                else:
                    nums[k] = temp[j]
                    j += 1
                    self.count += (mid - i + 1)
                k += 1
            while i <= mid:
                nums[k] = temp[i]
                k += 1
                i += 1
            while j <= right:
                nums[k] = temp[j]
                k += 1
                j += 1
        def merge_sort(nums, left, right):
            if left < right:
                mid = left + (right - left) // 2
                merge_sort(nums, left, mid)
                merge_sort(nums, mid+1, right)
                merge(nums, left, mid, right)

        self.count = 0
        merge_sort(nums, 0, len(nums) - 1)
        return self.count