题意:在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007
思路:O(n2)肯定不行,用的归并排序。(树状数组也可以)
class Solution {
public:const int mod = 1000000007;int InversePairs(vector<int> data) {if (data.size() == 0) return 0;vector<int> copy;for (int i = 0; i < data.size(); i++)copy.push_back(data[i]);return InverPairsCore(data,copy,0,data.size()-1);}int InverPairsCore(vector<int> &data, vector<int> ©, int l, int r){if (l == r){copy[l] = data[l];return 0;}int length =(r - l)/2;int mid = (l + r) / 2;//data是原始数据 copy是修改后的数据int left = InverPairsCore(copy, data, l, mid)%mod;int right = InverPairsCore(copy, data, mid + 1, r)%mod;int lend = mid;int rend = r;int index = r;int count = 0;while (lend >= l&&rend >= mid + 1){if (data[lend] > data[rend]){copy[index--] = data[lend--];count += rend - mid;count %= mod;}else{copy[index--] = data[rend--];}}for (; lend >= l;lend--)copy[index--] = data[lend];for (; rend >= mid + 1;rend--)copy[index--] = data[rend];//cout << left + right + count << endl;return (((left + right)%mod + count)%mod)%mod;}
};