一、题目描述

二、算法原理

三、代码实现

3.1升序：

class Solution 
{
public:int mergeSort(vector<int>& nums, int left, int right){if (left >= right){return 0;}int mid = left + (right - left) / 2, ret = 0;ret += mergeSort(nums, left, mid);ret += mergeSort(nums, mid + 1, right);//求一左一右vector<int> temp(right - left + 1);int cur1 = left, cur2 = mid + 1, i = 0;while (cur1 <= mid && cur2 <= right){if (nums[cur1] <= nums[cur2]){temp[i++] = nums[cur1++];}else{ret += (mid - cur1 + 1);temp[i++] = nums[cur2++];       }}while (cur1 <= mid) temp[i++] = nums[cur1++];while (cur2 <= right) temp[i++] = nums[cur2++];for (int i = left; i <= right; i++){nums[i] = temp[i - left];}return ret;}int reversePairs(vector<int>& record) {return mergeSort(record,0,record.size()-1);}
};

3.2降序：

class Solution 
{
public:int mergeSort(vector<int>& nums, int left, int right){if (left >= right){return 0;}int mid = left + (right - left) / 2, ret = 0;ret += mergeSort(nums, left, mid);ret += mergeSort(nums, mid + 1, right);//求一左一右vector<int> temp(right - left + 1);int cur1 = left, cur2 = mid + 1, i = 0;while (cur1 <= mid && cur2 <= right){if (nums[cur1] <= nums[cur2]){temp[i++] = nums[cur2++];}else{ret += (right-cur2+1);temp[i++] = nums[cur1++];       }}while (cur1 <= mid) temp[i++] = nums[cur1++];while (cur2 <= right) temp[i++] = nums[cur2++];for (int i = left; i <= right; i++){nums[i] = temp[i - left];}return ret;}int reversePairs(vector<int>& record) {return mergeSort(record,0,record.size()-1);}
};