【LCR 170. 交易逆序对的总数】

逆序对的总数】"/>

【LCR 170. 交易逆序对的总数】

目录

• 一、题目描述
• 二、算法原理
• 三、代码实现
• • 3.1升序：
  • 3.2降序：

一、题目描述

二、算法原理

三、代码实现

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);}
};