JZ51 数组中的逆序对

发表于 分类于 本文字数： 549 阅读时长 ≈ 2 分钟

JZ51 数组中的逆序对

描述

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

数据范围： 对于 $50%$ 的数据, $size≤10^4$，对于 $100%$ 的数据, $size≤10^5$，数组中所有数字的值满足 $0≤val≤10^9$

要求：空间复杂度 $O(n)$，时间复杂度 $O(nlogn)$

输入描述：题目保证输入的数组中没有的相同的数字

示例1

1
2
输入：[1,2,3,4,5,6,7,0]
返回值：7

示例2

1
2
输入：[1,2,3]
返回值：0

题解

写了半天，还用上链表了，实际上这题用归并排序会更好一些(好难，难怪这题中等还只有17左右AC率)。

归并排序的思想就是递归地每次考虑一半的数据，然后在合并时将其排序，递归的边界条件是单个数字天生具有有序性。对于这道题而言，可以借此来快速地判断右侧有多少元素小于某个元素。

归并的过程：

对于$nums$，我们处理$left$到$right$的部分，拿到以后首先划分左右两部分数组$(left,left+(right-1)/2)$与$(left+(right-1)/2+1,right)$。然后递归地归并这两部分。然后是具体地排序，比较左右两个数组，把更小的那个放置于新的数组中，边界条件是左侧数组或右侧数组用光，触发后把剩下的部分也都放到新数组中去即可。

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
class Solution {
public:
    int InversePairs(vector<int>& nums) {
        if(nums.empty()) return 0;
        vector<int> tmp(nums.size());
        return mergeSort(nums, tmp, 0, nums.size()-1);
    }
private:
    int mergeSort(vector<int>& nums, vector<int>& tmp, int l, int r){
        if(l >= r) return 0;
        int mid = l + (r-l)/2;
        int count = (mergeSort(nums, tmp, l, mid) + mergeSort(nums, tmp, mid+1, r)) % 1000000007;
        int i = mid, j = r, k = r;
        while(i >= l && j >= mid+1){
            if(nums[i] > nums[j]){
                count = (count + j-mid) % 1000000007;
                tmp[k--] = nums[i--];
            } else {
                tmp[k--] = nums[j--];
            }
        }
        while(i >= l) tmp[k--] = nums[i--];
        while(j >= mid+1) tmp[k--] = nums[j--];
        for(int t = l; t <= r; t++) nums[t] = tmp[t];
        return count;
    }
};