题目描述
在数组中的两个数字如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。
输入一个数组,求出这个数组中的逆序对的总数。
样例
输入:[1,2,3,4,5,6,0]
输出:6
C++ 代码
class Solution
{
public:
int inversePairs(vector<int>& nums)
{
merge(0, nums.size() - 1, nums);
return this->ret;
}
private:
void mergeSort(int left, int right, vector<int>& nums)
{
int mid = left + right >> 1;
vector<int>tmp;
int leftNow = left, rightNow = mid + 1;
while (leftNow <= mid && rightNow <= right)
{
if (nums[leftNow] <= nums[rightNow])tmp.push_back(nums[leftNow++]);
else
{
//mid 是重点
//mid - leftNow + 1; 原因是因为左边与右边都是从大到小排序好的
//所以现在左边大于右边,左边以后都大于右边,
//而右边该下标加一的位置大于等于该下标的数值,
//所以主while判下一个右边下标
this->ret += mid - leftNow + 1;
tmp.push_back(nums[rightNow++]);
}
}
while (leftNow <= mid)tmp.push_back(nums[leftNow++]);
while (rightNow <= right)tmp.push_back(nums[rightNow++]);
int idx = 0;
for (int i = left; i <= right; i++)
nums[i] = tmp[idx++];
}
private:
void merge(int left, int right, vector<int>& nums)
{
if (left >= right)return;
int mid = left + right >> 1;
merge(left, mid, nums), merge(mid + 1, right, nums);
mergeSort(left, right, nums);
}
private:
int ret = 0;
};