【C++算法】分治——归并

排序数组

• 题目链接

排序数组https://leetcode.cn/problems/sort-an-array/description/

• 算法原理

• 代码步骤

class Solution {vector<int> tmp;
public:vector<int> sortArray(vector<int>& nums) {tmp.resize(nums.size());merge(nums, 0, nums.size() - 1);return nums;}void merge(vector<int>& nums, int left, int right){if(left >= right) return;int mid = (right + left) >> 1;merge(nums, left, mid);merge(nums, mid + 1, right);int i = 0, cur1 = left, cur2 = mid + 1;while(cur1 <= mid && cur2 <= right){tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];}while(cur1 <= mid) tmp[i++] = nums[cur1++];while(cur2 <= right) tmp[i++] = nums[cur2++];for(int i = left; i <= right; i++){nums[i] = tmp[i - left];}}
};

交易逆序对的总数

• 题目链接

交易逆序对的总数https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/description/

• 算法原理

• 代码步骤

class Solution {vector<int> tmp;
public:int reversePairs(vector<int>& record) {tmp.resize(record.size());return merge(record, 0, record.size() - 1);}int merge(vector<int>& nums, int left, int right){int ret = 0;if(left >= right) return 0;int mid = (left + right) >> 1;ret += merge(nums, left, mid);ret += merge(nums, mid + 1, right);int i = 0, cur1 = left, cur2 = mid + 1;while(cur1 <= mid && cur2 <= right){if(nums[cur1] <= nums[cur2]) {tmp[i++] = nums[cur1++];}else{ret += mid - cur1 + 1;tmp[i++] = nums[cur2++];}}while(cur1 <= mid) tmp[i++] = nums[cur1++];while(cur2 <= right) tmp[i++] = nums[cur2++];for(int i = left; i <= right; i++){nums[i] = tmp[i - left];}return ret;}
};

计算右侧小于当前元素的个数

• 题目链接

计算右侧小于当前元素的个数https://leetcode.cn/problems/count-of-smaller-numbers-after-self/description/

• 算法原理

• 代码步骤

class Solution {vector<int> ret;vector<int> index;int tmpNums[100001];int tmpIndex[100001];
public:vector<int> countSmaller(vector<int>& nums) {int n = nums.size();ret.resize(n);index.resize(n);for(int i = 0; i < n; i++){index[i] = i;}mergeSort(nums, 0, n - 1);return ret;}void mergeSort(vector<int>& nums, int left, int right){if(left >= right) return;int mid = (left + right) >> 1;mergeSort(nums, left, mid);mergeSort(nums, mid + 1, right);int i = 0, cur1 = left, cur2 = mid + 1;while(cur1 <= mid && cur2 <= right){if(nums[cur1] <= nums[cur2]){tmpNums[i] = nums[cur2];tmpIndex[i++] = index[cur2++];}else{ret[index[cur1]] += right - cur2 + 1;tmpNums[i] = nums[cur1];tmpIndex[i++] = index[cur1++];}}while(cur1 <= mid) {tmpNums[i] = nums[cur1];tmpIndex[i++] = index[cur1++];}while(cur2 <= right){tmpNums[i] = nums[cur2];tmpIndex[i++] = index[cur2++];}for(int i = left; i <= right; i++){nums[i] = tmpNums[i - left];index[i] = tmpIndex[i - left];}}
};

翻转对

• 题目链接

翻转对https://leetcode.cn/problems/reverse-pairs/description/

• 算法原理

• 代码步骤

class Solution {vector<int> tmp;
public:int reversePairs(vector<int>& nums) {int n = nums.size();tmp.resize(n);return mergeSort(nums, 0, n - 1);}int mergeSort(vector<int>& nums, int left, int right){if(left >= right) return 0;int ret = 0;int mid = (left + right) >> 1;ret += mergeSort(nums, left, mid);ret += mergeSort(nums, mid + 1, right);int cur1 = left, cur2 = mid + 1, i = 0;while(cur1 <= mid && cur2 <= right){while(cur2 <= right && nums[cur1] / 2.0 <= nums[cur2]){cur2++;}ret += right - cur2 + 1;cur1++;}cur1 = left, cur2 = mid + 1;while(cur1 <= mid && cur2 <= right){if(nums[cur1] >= nums[cur2]) {tmp[i++] = nums[cur1++];}else{tmp[i++] = nums[cur2++];}}while(cur1 <= mid){tmp[i++] = nums[cur1++];}while(cur2 <= right){tmp[i++] = nums[cur2++];}for(int i = left; i <= right; i++){nums[i] = tmp[i - left];}return ret;}
};