找一个中间点,把左边排好序,右边排好序,那么整体就有序。而左边排序又是找一个中间点,把左边排好序,直到这个左边就行一个值,那么就返回,左边和右边排好,再把这两个有序数组合并,再向上返回,直到整个数组都有序。
在之前使用快排做过一次,这次使用归并排序来做。 先选择中间点划分区间,把左右区间排序。排好之后,再合并两个有序数组,就可以了,用递归来实现将所有元素进行排序。
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];
}
};
一、题目解析 只要前面的一个数大于后面的一个数,就可以构成一个逆序对。 如果直接用暴力枚举,会超出时间限制。
二、算法原理 可以把这个数组划分为两个部分,找出左边部分的逆序对a,再找出右边的逆序对b,然后一左一右又挑出来一个逆序对c,总的就是a+b+c。 可以做一下优化,左边挑完逆序对给左边排好序,右边挑完之后也排好序,然后再执行一左一右找逆序对。 就可以利用归并排序来解决这个问题。 如果以升序排列已经挑好的部分的数组。 在左边的cur1位置的值如果小于等于右边cur2位置的值,说明此时没有逆序对,然后将cur1继续往后走。 在左边的cur1位置的值如果大于右边cur2位置的值,说明cur1值和它之后的值都是大于cur2的,那么此是就有mid-cur1+1个逆序对,然后再比较cur1值和cur2++之后的值,看看能不能构成逆序对,能够成的话就又有mid-cur1+1个逆序对了。
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;
}
};
和上面那题一样,采用归并排序。找出当前元素右边有多少个数比我小,如果以降序排列已经挑好的部分的数组。 把数组放为两部分,先找到左边部分再找到右边部分的。 与上面那题不同的是,这里还要在对应的下标中返回结果,但是因为排序下标已经改变了,所以的建一个下标映射表,在原数据排序过程中下标表也跟这改变。
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];
}
}
};
和找逆序对那个题类似,这里以降序排降序。 也是按照中间元素划分区间,先计算左右两侧的翻转对,再计算翻转对的数量,就是再排好序。 对于任意给定的 left[cur1] 而言,我们不断地向右移动 cur2,直到 left[cur1] <= 2*right[cur2]。此时对于 right 数组而言,cur2 之前的元素全部都可以与 left[cur1] 构成翻转对。 随后,我们再将 cur1 向右移动一个单位,此时 cur2 指针并不需要回退(因为 left 数组是升序的)依旧往右移动直到 left[cur1] <= 2 * right[cur2]。不断重复这样的过程,就能够求出所有左右端点分别位于两个子数组的翻转对数目。
最后合并两个有序数组。
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;
}
};