面试题51. 数组中的逆序对

题目

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

示例 1:

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

限制：

0 <= 数组长度 <= 50000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

归并排序的时候，顺便统计一下哪些数字在我前面。

https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/solution/bao-li-jie-fa-fen-zhi-si-xiang-shu-zhuang-shu-zu-b/

如图所示，不过我用的开区间，比这个闭区间要简单。

代码

class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        self.count = 0
        self.merge(nums, 0, len(nums))
        return self.count

    def merge(self,nums, start, end):
        if end - start <= 1: return 
        mid = (start + end)//2
        self.merge(nums, start, mid)
        self.merge(nums, mid, end)
        nums_part = []
        i = start
        j = mid
        while i < mid and j < end:
            if nums[i] <= nums[j]:
                nums_part.append(nums[i])
                i += 1
            else:
                self.count += mid - i
                nums_part.append(nums[j])
                j += 1
        if i<mid: nums_part.extend(nums[i:mid])
        if j<end: nums_part.extend(nums[j:end])
        assert len(nums_part) == end-start
        nums[start:end] = nums_part