【优选算法】（第二十五篇）
目录
计算右侧⼩于当前元素的个数（hard）
题目解析
讲解算法原理
编写代码
翻转对（hard）
题目解析
讲解算法原理
编写代码
计算右侧⼩于当前元素的个数（hard）
题目解析
1.题目链接：. - 力扣（LeetCode）
2.题目描述
给你⼀个整数数组nums，按要求返回⼀个新数组counts。数组counts有该性质：counts[i]的值是nums[i]右侧⼩于nums[i]的元素的数量。
⽰例1：
输⼊：nums=[5,2,6,1]
输出：[2,1,1,0]
解释：
5的右侧有2个更⼩的元素(2和1)
2的右侧仅有1个更⼩的元素(1)
6的右侧有1个更⼩的元素(1)
1的右侧有0个更⼩的元素
讲解算法原理
解法（归并排序）：
算法思路：
这⼀道题的解法与求数组中的逆序对的解法是类似的，但是这⼀道题要求的不是求总的个数，⽽是要返回⼀个数组，记录每⼀个元素的右边有多少个元素⽐⾃⼰⼩。
但是在我们归并排序的过程中，元素的下标是会跟着变化的，因此我们需要⼀个辅助数组，来将数组元素和对应的下标绑定在⼀起归并，也就是再归并元素的时候，顺势将下标也转移到对应的位置上。
由于我们要快速统计出某⼀个元素后⾯有多少个⽐它⼩的，因此我们可以利⽤求逆序对的第⼆种⽅法。
算法流程：
• 创建两个全局的数组：
vector<int>index：记录下标vector<int>ret：记录结果
index⽤来与原数组中对应位置的元素绑定，ret⽤来记录每个位置统计出来的逆序对的个数。
• countSmaller()主函数：
a. 计算nums数组的⼤⼩为n；b. 初始化定义的两个全局的数组；
i. 为两个数组开辟⼤⼩为n的空间ii. index初始化为数组下标；
iii. ret初始化为0c. 调⽤mergeSort()函数，并且返回ret结果数组。
• voidmergeSort(vector<int>&nums,intleft,intright)函数：
函数设计：通过修改全局的数组ret，统计出每⼀个位置对应的逆序对的数量，并且排序；⽆需返回值，因为直接对全局变量修改，当函数结束的时候，全局变量已经被修改成最后的结果。
• mergeSort()函数流程：
a. 定义递归出⼝：left>=right时，直接返回；b. 划分区间：根据中点mid，将区间划分为[left,mid]和[mid+1,right]；c. 统计左右两个区间逆序对的数量：
i. 统计左边区间[left,mid]中每个元素对应的逆序对的数量到ret数组中，并排序；ii. 统计右边区间[mid+1,right]中每个元素对应的逆序对的数量到ret数组中，并排序。
d. 合并左右两个有序区间，并且统计出逆序对的数量：
i. 创建两个⼤⼩为right-left+1⼤⼩的辅助数组：
• numsTmp：排序⽤的辅助数组；
• indexTmp：处理下标⽤的辅助数组。
ii. 初始化遍历数组的指针：cur1=left（遍历左半部分数组）cur2=mid+1（遍历右半边数
组）dest=0（遍历辅助数组）curRet（记录合并时产⽣的逆序对的数量）；iii. 循环合并区间：
• 当nums[cur1]<=nums[cur2]时：
◦ 说明此时[mid+1,cur2)之间的元素都是⼩于nums[cur1]的，需要累加到ret数
组的indext[cur1]位置上（因为index存储的是元素对应位置在原数组中的下标）◦ 归并排序：不仅要将数据放在对应的位置上，也要将数据对应的坐标也放在对应的位
置上，使数据与原始的下标绑定在⼀起移动。• 当nums[cur1]>nums[cur2]时，⽆需统计，直接归并，注意index也要跟着归并。
iv. 处理归并排序中剩余的元素；
• 当左边有剩余的时候，还需要统计逆序对的数量；• 当右边还有剩余的时候，⽆需统计，直接归并。
v. 将辅助数组的内容替换到原数组中去；
编写代码
c++算法代码：
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];
}
}
};java算法代码：
class Solution
{
int[] ret;
int[] index; // 标记 nums 中当前元素的原始下标
int[] tmpIndex;
int[] tmpNums;
public List<Integer> countSmaller(int[] nums)
{
int n = nums.length;
ret = new int[n];
index = new int[n];
tmpIndex = new int[n];
tmpNums = new int[n];
// 初始化 index 数组
for(int i = 0; i < n; i++)
index[i] = i;
mergeSort(nums, 0, n - 1);
List<Integer> l = new ArrayList<Integer>();
for(int x : ret)
l.add(x);
return l;
}
public void mergeSort(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) // 降序排序 {
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];
}
}
}
翻转对（hard）
题目解析
1.题目链接：. - 力扣（LeetCode）
2.题目描述
给定⼀个数组nums，如果i<j且nums[i]>2*nums[j]我们就将(i,j)称作⼀个重要翻转对。你需要返回给定数组中的重要翻转对的数量。
⽰例1:
输⼊:[1,3,2,3,1]输出:2
题⽬解析：
翻转对和逆序对的定义⼤同⼩异，逆序对是前⾯的数要⼤于后⾯的数。⽽翻转对是前⾯的⼀个数要⼤于后⾯某个数的两倍。因此，我们依旧可以⽤归并排序的思想来解决这个问题。
讲解算法原理
解法（归并排序）：算法思路：
⼤思路与求逆序对的思路⼀样，就是利⽤归并排序的思想，将求整个数组的翻转对的数量，转换成三部分：左半区间翻转对的数量，右半区间翻转对的数量，⼀左⼀右选择时翻转对的数量。重点就是在合并区间过程中，如何计算出翻转对的数量。
与上个问题不同的是，上⼀道题我们可以⼀边合并⼀遍计算，但是这道题要求的是左边元素⼤于右边元素的两倍，如果我们直接合并的话，是⽆法快速计算出翻转对的数量的。
例如left=[4,5,6]right=[3,4,5]时，如果是归并排序的话，我们需要计算left数组中有多少个能与3组成翻转对。但是我们要遍历到最后⼀个元素6才能确定，时间复杂度较⾼。
因此我们需要在归并排序之前完成翻转对的统计。下⾯依旧以⼀个⽰例来模仿两个有序序列如何快速求出翻转对的过程：假定已经有两个已经有序的序列left=[4,5,6]right=[1,2,3]。
⽤两个指针cur1cur2遍历两个数组。
◦ 对于任意给定的left[cur1]⽽⾔，我们不断地向右移动cur2，直到left[cur1]<=2*
right[cur2]。此时对于right数组⽽⾔，cur2之前的元素全部都可以与left[cur1]构成翻转对。
◦ 随后，我们再将cur1向右移动⼀个单位，此时cur2指针并不需要回退（因为left数组是升序
的）依旧往右移动直到left[cur1]<=2*right[cur2]。不断重复这样的过程，就能够求出所有左右端点分别位于两个⼦数组的翻转对数⽬。
由于两个指针最后都是不回退的的扫描到数组的结尾，因此两个有序序列求出翻转对的时间复杂度是O(N)。
综上所述，我们可以利⽤归并排序的过程，将求⼀个数组的翻转对转换成求左数组的翻转对数量+右数组中翻转对的数量+左右数组合并时翻转对的数量。
编写代码
降序版本
c++代码实现：
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;
}
};java算法代码：
class Solution
{
int[] tmp;
public int reversePairs(int[] nums)
{
int n = nums.length;
tmp = new int[n];
return mergeSort(nums, 0, n - 1);
}
public int mergeSort(int[] nums, int left, int right)
{
if(left >= right) return 0;
int ret = 0;
// 1. 根据中间元素，将区间分成两部分
int mid = (left + right) / 2;
// [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;
}
}升序版本：
c++算法代码：
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(cur2 <= right) // 升序的情况
{
while(cur1 <= mid && nums[cur2] >= nums[cur1] / 2.0) cur1++;
if(cur1 > mid)
break;
ret += mid - cur1 + 1;
cur2++;
}
// 4. 合并两个有序数组
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 j = left; j <= right; j++)
nums[j] = tmp[j];
return ret;
}
};java算法代码：
class Solution
{
int[] tmp;
public int reversePairs(int[] nums)
{
int n = nums.length;
tmp = new int[n];
return mergeSort(nums, 0, n - 1);
}
public int mergeSort(int[] nums, int left, int right)
{
if(left >= right) return 0;
int ret = 0;
// 1. 根据中间元素，将区间分成两部分
int mid = (left + right) / 2;
// [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(cur2 <= right)
{
while(cur1 <= mid && nums[cur2] >= nums[cur1] / 2.0) cur1++;
if(cur1 > mid)
break;
ret += mid - cur1 + 1;
cur2++;
}
// 4. 合并两个有序数组 - 升序
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 j = left; j <= right; j++)
nums[j] = tmp[j];
return ret;
}
}