目录

0493:翻转对(★★)

力扣第 493 题

题目

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

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

示例 1:

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

示例 2:

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

注意:

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

相似问题:

分析

  • 遍历 j,找 nums[:j] 中大于 2*nums[j] 的个数。
  • 容易想到用有序集合维护 nums[:j],二分查找即可

解答

1
2
3
4
5
6
7
8
class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        from sortedcontainers import SortedList
        res, sl = 0, SortedList()
        for x in nums:
            res += len(sl)-sl.bisect_right(x*2)
            sl.add(x)
        return res

479 ms

*附加

还可以用 cdq 分治。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        def cdq(A,l,r):
            if l==r:
                return 0
            m = (l+r)//2
            B,C = [],[]
            for i in A:
                (C if i>m else B).append(i)
            res = cdq(B,l,m)+cdq(C,m+1,r)
            k = 0
            for i in C:
                while k<len(B) and nums[B[k]]<=2*nums[i]:
                    k += 1
                res += len(B)-k
            return res
        n = len(nums)
        A = sorted(range(n),key=lambda i:nums[i])
        return cdq(A,0,n-1)

743 ms