【算法】分治-归并
归并
找一个中间点，把左边排好序，右边排好序，那么整体就有序。而左边排序又是找一个中间点，把左边排好序，直到这个左边就行一个值，那么就返回，左边和右边排好，再把这两个有序数组合并，再向上返回，直到整个数组都有序。
1. 912. 排序数组
1.1 分析
在之前使用快排做过一次，这次使用归并排序来做。 先选择中间点划分区间，把左右区间排序。排好之后，再合并两个有序数组，就可以了，用递归来实现将所有元素进行排序。
1.2 代码
class Solution
{
vector<int> tmp;
public:
vector<int> sortArray(vector<int>& nums)
{
tmp.resize(nums.size());
mergeSort(nums, 0, nums.size() - 1);
return nums;
}
void mergeSort(vector<int>& nums, int left, int right)
{
if (left >= right) return;
// 1. 选择中间点划分区间
int mid = (left + right) /2;
// [left, mid] [mid + 1, right]
// 2. 把左右区间排序
mergeSort(nums, left, mid);
mergeSort(nums, mid + 1, right);
// 3. 合并两个有序数组
int cur1 = left, cur2 = mid + 1, i = 0;
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++];
// 4. 还原数组
for (int i = left; i <= right; i++)
nums[i] = tmp[i - left];
}
};2. LCR 170. 交易逆序对的总数
2.1 分析
一、题目解析 只要前面的一个数大于后面的一个数，就可以构成一个逆序对。 如果直接用暴力枚举，会超出时间限制。
二、算法原理 可以把这个数组划分为两个部分，找出左边部分的逆序对a，再找出右边的逆序对b，然后一左一右又挑出来一个逆序对c，总的就是a+b+c。 可以做一下优化，左边挑完逆序对给左边排好序，右边挑完之后也排好序，然后再执行一左一右找逆序对。 就可以利用归并排序来解决这个问题。 如果以升序排列已经挑好的部分的数组。 在左边的cur1位置的值如果小于等于右边cur2位置的值，说明此时没有逆序对，然后将cur1继续往后走。 在左边的cur1位置的值如果大于右边cur2位置的值，说明cur1值和它之后的值都是大于cur2的，那么此是就有mid-cur1+1个逆序对，然后再比较cur1值和cur2++之后的值，看看能不能构成逆序对，能够成的话就又有mid-cur1+1个逆序对了。
2.2 代码
class Solution {
int tmp[500010];
public:
int reversePairs(vector<int>& nums)
{
return mergeSort(nums, 0, nums.size()-1);
}
int mergeSort(vector<int>& nums, int left, int right)
{
if (left >= right)return 0;
int ret = 0;
//找中间点
int mid = (left + right) >>1;
//[left,mid][mid+1,right]
//找左边逆序对+右边逆序对+左右两边排序
ret += mergeSort(nums, left, mid);
ret += mergeSort(nums, mid + 1, right);
//一左一右统计逆序对
int cur1 = left, cur2 = mid + 1, i = 0;
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 j = left; j <= right; j++)
nums[j] = tmp[j - left];
return ret;
}
};3. 315. 计算右侧小于当前元素的个数
3.1 分析
和上面那题一样，采用归并排序。找出当前元素右边有多少个数比我小，如果以降序排列已经挑好的部分的数组。 把数组放为两部分，先找到左边部分再找到右边部分的。 与上面那题不同的是，这里还要在对应的下标中返回结果，但是因为排序下标已经改变了，所以的建一个下标映射表，在原数据排序过程中下标表也跟这改变。
3.2 代码
class Solution {
vector<int> ret;
vector<int> index; // 记录 nums 中当前元素的原始下标
int tmpNums[500010];
int tmpIndex[500010];
public:
vector<int> countSmaller(vector<int>& nums)
{
int n = nums.size();
ret.resize(n);
index.resize(n);
// 初始化⼀下 index 数组
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;
// 1. 根据中间元素，划分区间
int mid = (left + right) >> 1;
// [left, mid] [mid + 1, right]
// 2. 先处理左右两部分
mergeSort(nums, left, mid);
mergeSort(nums, mid + 1, right);
// 3. 处理⼀左⼀右的情况
int cur1 = left, cur2 = mid + 1, i = 0;
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++];
}
}
// 4. 处理剩下的排序过程
while (cur1 <= mid)
{
tmpNums[i] = nums[cur1];
tmpIndex[i++] = index[cur1++];
}
while (cur2 <= right)
{
tmpNums[i] = nums[cur2];
tmpIndex[i++] = index[cur2++];
}
for (int j = left; j <= right; j++)
{
nums[j] = tmpNums[j - left];
index[j] = tmpIndex[j - left];
}
}
};4. 493. 翻转对
4.1 分析
和找逆序对那个题类似，这里以降序排降序。 也是按照中间元素划分区间，先计算左右两侧的翻转对，再计算翻转对的数量，就是再排好序。 对于任意给定的 left[cur1] 而言，我们不断地向右移动 cur2，直到 left[cur1] <= 2*right[cur2]。此时对于 right 数组而言，cur2 之前的元素全部都可以与 left[cur1] 构成翻转对。 随后，我们再将 cur1 向右移动一个单位，此时 cur2 指针并不需要回退（因为 left 数组是升序的）依旧往右移动直到 left[cur1] <= 2 * right[cur2]。不断重复这样的过程，就能够求出所有左右端点分别位于两个子数组的翻转对数目。
最后合并两个有序数组。
4.2 代码
class Solution
{
int tmp[50010];
public:
int reversePairs(vector<int>& nums)
{
return mergeSort(nums, 0, nums.size() - 1);
}
int mergeSort(vector<int>& nums, int left, int right)
{
if (left >= right) return 0;
int ret = 0;
// 1. 先根据中间元素划分区间
int mid = (left + right) >> 1;
// [left, mid] [mid + 1, right]
// 2. 先计算左右两侧的翻转对
ret += mergeSort(nums, left, mid);
ret += mergeSort(nums, mid + 1, right);
// 3. 先计算翻转对的数量
int cur1 = left, cur2 = mid + 1, i = left;
while (cur1 <= mid) // 降序的情况
{
while (cur2 <= right && nums[cur2] >= nums[cur1] / 2.0) cur2++;
if (cur2 > right)
break;
ret += right - cur2 + 1;
cur1++;
}
// 4. 合并两个有序数组
cur1 = left, cur2 = mid + 1;
while (cur1 <= mid && cur2 <= right)
tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur2++] : nums[cur1++];
while (cur1 <= mid) tmp[i++] = nums[cur1++];
while (cur2 <= right) tmp[i++] = nums[cur2++];
for (int j = left; j <= right; j++)
nums[j] = tmp[j];
return ret;
}
};腾讯云开发者
