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

问题描述

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

 

示例 1:

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

 

限制：

0 <= 数组长度 <= 50000

解题思路

问题是要计算 \(\sum_{i=0}^{n-1}\sum_{j=0}^{i-1}\mathcal{I}(\texttt{nums[j]}\gt\texttt{nums}[i])\)。

如果 \(\texttt{nums}[i]\) 的左边数据已经有序，那么直接使用二分查找就可以得到 \(\texttt{nums}[i]\) 结尾的逆序对数量。

但是到 \(i+1\) 时，需要把 \(\texttt{nums}[i]\) 插入到有序数组中使得数据重新有序，而插入操作涉及到数据的移动，导致时间复杂度为 \(\mathcal{O}(n^2)\)。

在 Python 中使用 nums[i:i]=[x] 的插入语法十分高效，可以通过这道题，而且基本上是耗时最短的方法。

class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        ans = 0
        s = []

        for x in nums:
            i = bisect_right(s, x)
            ans += len(s) - i
            s[i:i] = [x]

        return ans

而如果使用 C++ 中的 vector.insert 操作则会导致超时。

返回顶部

在手机上阅读