数组中的逆序对

Desicription

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

Solution

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
42
43
44
class Solution {
private:
    int count = 0;
    void Merge(vector<int>& data, int left, int right) {
        int mid = (left + right) >> 1;
        int i = left;
        int j = mid + 1;
        int k = right;
        vector<int> tmp;
        while(i <= mid && j <= right) {
            if(data[i] <= data[j]) {
                tmp.emplace_back(data[i++]);
            } else {
                count += mid - i + 1;
                count %= 1000000007;
                tmp.emplace_back(data[j++]);
            }
        }
        while(i <= mid) {
            tmp.emplace_back(data[i++]);
        }
        while(j <= right) {
            tmp.emplace_back(data[j++]);
        }
        int index = 0;
        for(int a = left; a <= right; a++) {
            data[a] = tmp[index++];
        }

    }
    void MergeSort(vector<int>& data, int left, int right) {
        if(left < right) {
            int mid = (left + right) >> 1;
            MergeSort(data, left, mid);
            MergeSort(data, mid + 1, right);
            Merge(data, left, right);
        }
    }
public:
    int InversePairs(vector<int> data) {
        MergeSort(data, 0, data.size() - 1);
        return count;
    }
};