翻转对

难度: Hard

给定一个数组 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个重要翻转对。

你需要返回给定数组中的重要翻转对的数量。

示例 1:

输入: [1,3,2,3,1]
输出: 2

示例 2:

输入: [2,4,3,5,1]
输出: 3

注意:

给定数组的长度不会超过50000。
输入数组中的所有数字都在32位整数的表示范围内。

Submission

运行时间: 479 ms

内存: 22.7 MB

class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        # n = len(nums)
        # res = 0
        # for i in range(n-1):
        #     for j in range(i+1, n):
        #         if nums[i] > 2*nums[j]:
        #             res +=1
        # return res
        self.count = 0
        def merge_sort(nums):
            n = len(nums)
            if n <= 1:
                return nums
            mid = n // 2
            left = merge_sort(nums[:mid])
            right = merge_sort(nums[mid:])
            # 归并排序好两部分后，计算这两个部分‘间’满足要求的数量
            i,j = mid-1, len(right)-1
            while i >= 0:
                while j >= 0 and left[i] <= right[j]*2:
                    j -= 1
                self.count += j+1
                i -= 1

            nums = merge(left, right)
            return nums

        def merge(left, right):
            result = []
            i, j = 0,0
            while i< len(left) and j< len(right):
                if left[i] <= right[j]:
                    result.append(left[i])
                    i += 1
                else:
                    result.append(right[j])
                    j += 1
            result += left[i:] 
            result += right[j:]
            return result
        merge_sort(nums)
        return self.count

Explain

本题解采用了分治策略结合归并排序的方法来解决问题。首先，通过递归地将数组分解为更小的子数组，直到每个子数组只包含一个元素。然后，在归并排序的过程中，将这些子数组合并回去，并在合并的同时计算两个子数组之间可能的重要翻转对的数量。具体来说，在合并两个已排序的子数组时，对于左边数组的每个元素，查找右边数组中满足条件（左边元素大于右边元素的两倍）的元素的数量，并累加到总计数中。最后返回这个计数值。

时间复杂度: O(n log n)

空间复杂度: O(n)

class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        self.count = 0
        def merge_sort(nums):
            n = len(nums)
            if n <= 1:
                return nums
            mid = n // 2
            left = merge_sort(nums[:mid])
            right = merge_sort(nums[mid:])
            i, j = mid-1, len(right)-1
            while i >= 0:
                while j >= 0 and left[i] <= right[j]*2:
                    j -= 1
                self.count += j+1
                i -= 1
            nums = merge(left, right)
            return nums
        def merge(left, right):
            result = []
            i, j = 0, 0
            while i < len(left) and j < len(right):
                if left[i] <= right[j]:
                    result.append(left[i])
                    i += 1
                else:
                    result.append(right[j])
                    j += 1
            result += left[i:]
            result += right[j:]
            return result
        merge_sort(nums)
        return self.count

Explore

归并排序是一种有效的排序算法，它通过分治法将数组分解为更小的子数组，分别对它们进行排序，然后将它们合并。在处理翻转对问题时，归并排序的分治策略允许我们在合并阶段同时计算翻转对的数量。这是因为在每次合并操作时，左右两个子数组都已经是排序好的状态，可以直接应用双指针技术来高效地计算满足条件的对数。此外，归并排序的时间复杂度为O(n log n)，适合处理大数据量，符合本题中数据规模的需求。

在归并排序的翻转对问题中，我们需要找到所有满足`nums[i] > 2*nums[j]`且`i < j`的对数。在此设置中，左数组的索引始终小于右数组的索引，因此我们需要检查左数组中的每个元素是否存在对应的右数组中的元素满足此条件。如果从右数组开始，我们无法有效地统计满足条件的索引对，因为右数组的元素索引是大于左数组的，不满足`i < j`的要求。

归并排序在递归过程中需要额外的空间来存储临时的子数组，对于每个递归调用，都需要为左右子数组分配空间。归并排序的空间复杂度总体上是O(n)，因为尽管在每层递归中都需要分配空间，但这些空间在每层递归后都会被释放。因此，尽管递归深度影响了空间的临时分配，但总体空间需求并不会超过输入数组的大小。