题目描述
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
分析：利用归并排序的思想，分成2部分，每一部分按照从大到小排序，然后比较左侧的a[i]和右侧的b[j]
若a[i]>b[j],那么a[j]大于b[j]~b[right], 产生 right-j+1 组逆序对。
若a[j]<=b[j],不产生逆序对。
同时更新数组的从left到right部分，实现其从大到小排序，然后在拿排序号的数组和更大的数组进行排序，同时计算逆序组的数量。
class Solution {
private:
int merge(vector<int>& data, int left, int mid, int right)
{
vector<int> tmpVec;
int cnt = ;
int i = left, j = mid + ;
// sort vecotr from big to small
while(i <= mid && j <= right)
{
if(data[i] > data[j])
{
cnt += (right - j + );
tmpVec.push_back(data[i]);
i++;
}
else
{
tmpVec.push_back(data[j]);
j++;
}
}
while(i <= mid)
{
tmpVec.push_back(data[i]);
i++;
}
while(j <= right)
{
tmpVec.push_back(data[j]);
j++;
}
//copy tmp data to original data
for(int k = ; k <= (right - left); k++)
{
data[k + left] = tmpVec[k];
}
return cnt;
}
int inversePairs(vector<int>& data, int left, int right)
{
if(data.size() == )
return ;
if(left >= right)
return ;
int mid = (left + right)/;
int cnt = ;
cnt += inversePairs(data, left, mid);
cnt += inversePairs(data, mid + , right);
cnt += merge(data, left, mid, right);
return cnt;
}
public:
int InversePairs(vector<int> data)
{
return inversePairs(data, , data.size() - );
}
};