493. Reverse Pairs (Count Inversion）变种

编程算法
#1 
class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        def helper_merge_sort(nums):
            if len(nums) <=1:
                return nums, 0
            res = []
            N = len(nums)
            l, lc = helper_merge_sort(nums[:N//2])
            r, rc = helper_merge_sort(nums[N//2:])
            i, j, ans = 0, 0, lc + rc
            while i < len(l) and j < len(r):
                if nums[i] > 2 * nums[j]:
                    res.append(nums[j])
                    j += 1
                    ans += j
                else:
                    if nums[i] <= nums[j]:
                        res.append(nums[i])
                        i += 1
                    else:
                        res.append(nums[j])
                        j += 1
            while i < len(l):
                res.append(nums[i])
                ans += j
                i += 1
            while j < len(r):
                res.append(nums[j])
                j += 1
            return res, ans
        return helper_merge_sort(nums)[1]

line 12, 我只在满足nums[i] > 2 * nums[j] 这个条件的时候 ans += j，其他时候正常merge，我不知道我逻辑上错在哪里了。

#2

Stacy你好，抱歉晚回复了。

这里你的逻辑有点乱哈。我们先按照正常的“谁小移动谁”的merge sort的规则来做。这里，根据你的代码，变量l和r分别指向左右两边排好序的子数组，对吧？所以接下来的merge过程要在这两个上面做，而你现在的代码确实在nums上面。这是第一个错误。

第二个，你这么来想，当l[i] < r[j]的时候，我们可以直接简单粗暴地从r[0]开始一直到找到第一个k使得2 * r[k] >= l[i]，那么这时候我们知道在右半边对于l[i]有k个数满足题目条件，对吧？重点来了，接下来，假设l[i + 1] > r[j + 1], r[j + 2], … 直到我们再一次遇到一个下标t使得l[i + 1] < r[t]的时候，为了找到对于l[i + 1]满足题目条件的在右边边的数，我们是不是可以直接从上一次的下标k开始不断重复题目要求的条件判断？

因为这个下标只会向前移动，永远不会回撤。所以我们只要在O(n)的时间内，就可以得到所有左半边的数的判定结果。加上原来merge的O(n)，我们总的，在除去递归开销剩余的overhead当中，时间复杂度还是O(n)。所以最终总的时间还是和merge sort一样，是O(nlogn)。

1 个赞