0%

数组中的逆序对

发表于 更新于

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

自左向右归并，数逆序数

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
45
46
47
48
49
50
class Solution
{
public:
    vector<int>::iterator it;
    int InversePairs(vector<int> &data)
    {
        it = data.begin();
        if (data.empty())
        {
            return 0;
        }
        vector<int> temp(data);
        return merge_sort(data.begin(), data.end(), temp.begin());
    }
    int merge_sort(const vector<int>::iterator data_begin, const vector<int>::iterator data_end, const vector<int>::iterator temp_begin)
    {
        int data_len = data_end - data_begin;
        if (data_len < 2)
        {
            return 0;
        }
        int mid_len = (data_len + 1) >> 1;
        auto data_mid = data_begin + mid_len, temp_mid = temp_begin + mid_len, temp_end = temp_begin + data_len;
        long long pair_counter = merge_sort(temp_begin, temp_mid, data_begin) + merge_sort(temp_mid, temp_end, data_mid), current_counter = 0;
        auto left = data_mid - 1, right = data_end - 1;
        for (auto dst = temp_end - 1; left >= data_begin && right >= data_mid; dst--)
        {
            if (*left > *right)
            {
                *dst = *left;
                current_counter += right - data_mid + 1;
                left--;
            }
            else
            {
                *dst = *right;
                right--;
            }
        }
        if (left >= data_begin)
        {
            copy(data_begin, left + 1, temp_begin);
        }
        else if (right >= data_mid)
        {
            copy(data_mid, right + 1, temp_begin);
        }
        return (pair_counter + current_counter) % 1000000007;
    }
};