class Solution
{
int res =
0;
// 并
void Merge(vector<
int> &target, vector<
int> ©,
int left,
int right,
int mid)
{
int i = left;
// 左半部分的索引
int j = mid +
1;
// 右半部分的索引
int k =
0;
// 被插入数组的索引
while (i <= mid && j <=
right)
{
if (target[i] >
target[j])
{
res += mid - i +
1;
res%=
1000000007;
copy[k++] = target[j++
];
}
else
copy[k++] = target[i++
];
}
while (i <=
mid)
copy[k++] = target[i++
];
while (j <=
right)
copy[k++] = target[j++
];
k =
0;
while (left <=
right)
{
target[left++] = copy[k++
];
}
}
// 归
void MergeSort(vector<
int> &target, vector<
int> ©,
int left,
int right)
{
if (left <
right)
{
int mid = (left + right) /
2;
MergeSort(target, copy, left, mid);
MergeSort(target, copy, mid +
1, right);
Merge(target, copy, left, right, mid);
}
}
void MergeSort(vector<
int> &
target)
{
vector<
int>
copy(target.size());
MergeSort(target, copy, 0, target.size() -
1);
}
public:
int InversePairs(vector<
int>
data)
{
if (data.size() ==
0)
return 0;
MergeSort(data);
return res;
}
};
题目描述
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007
输入描述:
题目保证输入的数组中没有的相同的数字
数据范围：
对于%50的数据,size<=10^4
对于%75的数据,size<=10^5
对于%100的数据,size<=2*10^5
示例1
输入
1,2,3,4,5,6,7,0
输出
7
在归并排序过程中，利用“并”时的比较来记录逆序对的次数（即左半部分的数字大于右半部分的数字的时候）
转载于:https://www.cnblogs.com/ruoh3kou/p/10137014.html
