剑指35-数组中的逆序对

Posted on | In |

问题

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。 并将P对1000000007取模的结果输出。 即输出P%1000000007

  • 分治和递归。将序列每次折半划分成两个子数组，对应两个子问题。两个子问题解决了，即得到子序列的逆序对数量之后，再统计分别在两个子序列的逆序对的数量，加起来就是原问题的逆序对数量。
  • 归并排序。如果两个子序列都是已经排好序的，统计分别在两个子序列的逆序对的数量就有复杂度低的方法，那么就需要对已经拍好序的两个子序列合并成一个排好序的序列，这其实就是归并排序要做的。

难点在于如何在归并过程中统计分别在两个子序列的逆序对的数量。核心代码：左子序列left..mid，右子序列mid+1..high，i和j分别是左、右子序列上的指针。

  • 其中mid-i+1是左子序列上与右子序列的元素nums[j]形成逆序对的所有元素数量，即i..mid位置的元素，将其标记为x(j)。那么只要把右子序列所有元素的x(j)计算并求和即可得到所有逆序对的数量。
    • x(j)是互斥且完备的。
  • x(j)=mid-i+1的理解：当要添加nums[j]到辅助数组时，说明nums[i]>nums[j]，且nums[i..mid]>nums[j]，一共有mid-i+1个逆序对。
    • 从小到大归并时，是从前往后的顺序，只能是计算x(j)，也就是添加nums[j]时计算。若要计算x(j)进而求和获得左右子序列的逆序对数，那么需要从大到小归并，且从后向前的顺序。
1
2
3
4
5
6
7
8
while i <= mid and j <= high:
    if nums[i] > nums[j]:
        temp.append(nums[j])
        xcount += mid-i+1
        j += 1
    else:
        temp.append(nums[i])
        i += 1

完整代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution:
    def InversePairs(self, nums):
        if not nums or len(nums) <= 1:
            return 0
        return self.mergeSort(nums, 0, len(nums)-1) % 1000000007
        
    def mergeSort(self, nums, low, high):
        if low >= high:
            return 0
        # 下面三行是分治的架构， left和right分别是两个分支数组所拥有的逆序对   
        mid = int((low + high) / 2)
        lcount = self.mergeSort(nums, low, mid)
        rcount = self.mergeSort(nums, mid+1, high)
        
        # 分治之后的合并，用了归并算法 
        # 下面代码有两个任务：1.统计归并过程中新发现的逆序对数量；2.使合并得到的新数组按顺序排列
        xcount = 0 # 用于统计归并过程中发现的新的逆序对     
        i = low
        j = mid+1
        temp = []
        
        # 以下是归并排序，只有xcount += mid-i+1是统计新的的逆序对数量
        while i <= mid and j <= high:
            if nums[i] > nums[j]:
                temp.append(nums[j])
                xcount += mid-i+1
                j += 1
            else:
                temp.append(nums[i])
                i += 1
        while i <= mid:
            temp.append(nums[i])
            i += 1
        while j <= high:
            temp.append(nums[j])
            j += 1
        # 将排好序的子序列拷贝到nums
        for i in range(low, high+1):
            nums[i] = temp[i-low]
        
        return xcount + lcount + rcount