一、剑指offer51---数组中的逆序对
题目链接:
LCR 170. 交易逆序对的总数 - 力扣（LeetCode）
题目介绍：
在数组中的两个数字，如果前面⼀个数字大于后面的数字，则这两个数字组成⼀个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
示例1:
- 输入:[7,5,6,4]
- 输出: 5
0 <= record.length <= 50000
思路：
首先暴力解法就是先确定一个元素，然后遍历数组，找有多少个比他小的数，就是简单的两个循环，但是暴力解法是一定会超时的。
接下来讲解一下更高效的方法。要求一个区间的所有的逆序对，我们可以将数组分为两部分，那结果就是 左部分的所有的逆序对 + 右部分的逆序对 + 一左一右选择的逆序对 ，会发现这个过程非常像归并排序的过程，所以们就往这个思路上想。
如果单纯的按上面的步骤写，其实还是暴力的解法，但是如果我们在找到逆序逆序对后数组顺便排下序，这样找逆序对就会很快，排序并不会改变逆序对的个数，可以找一个例子验证一下。
最核心的问题，如何在合并两个有序数组的过程中，统计出逆序对的数量？
合并两个有序序列时求逆序对的方法有两种：
- 在右边选一个数，看左边哪个比他大
- 在左边选一个数，看右边哪个比他小
方式1：在右边选一个数，看左边哪个比他小
- 假设我们排的是升序：
假设此时如果 nums[begin1] <= nums[begin2] ,由于当前是升序，往后遍历也不会有元素比nums[begin1] 小，所以可以让begin1++，如果 nums[begin1] > nums[begin2] 的话，由于是升序的，所以从begin1 到 mid 之间的元素都大于nums[begin2] ，都符合逆序对，此时左部分可以与nums[begin2]组成逆序对的个数都统计出来了，就可以让begin2++，按照这个思路这个题目的事件复杂度和归并排序是一样的。
- 那按照降序行不行呢？
我们来模拟一下，假设此时如果 nums[begin1] > nums[begin2] ,由于数组是降序那从begin到begin1之间的元素都大于nums[begin2] ，都可以与他构成逆序对，但是此时可以与nums[begin2]g构成逆序对的元素还没找完，因为不能确定begin1后面的元素是否还大于nums[begin2]。所以只能让begin1++，如果对应的这个元素仍然大于nums[begin2],我们就要继续计算begin 到 begin1 之间的元素，这样就会有重复的数据，所以方式一只能按升序处理
class Solution {
int tmp[50010];
public:
int reversePairs(vector<int>& record) {
return MergeSort(record,0,record.size()-1);
}
int MergeSort(vector<int>& record,int begin,int end)
{
if(begin>=end) return 0;
int mid=(begin+end)/2;
int ret=0;
ret+=MergeSort(record,begin,mid);
ret+=MergeSort(record,mid+1,end);
//处理一左一右
int begin1=begin,end1=mid;
int begin2=mid+1,end2=end;
int j=0;
while(begin1<=end1&&begin2<=end2)
{
if(record[begin1]<=record[begin2])
{
//处理排序，顺便让begin1向后遍历
tmp[j++]=record[begin1++];
}
else
{
ret+=(mid-begin1+1);
tmp[j++]=record[begin2++];
}
}
while(begin1<=end1) tmp[j++]=record[begin1++];
while(begin2<=end2) tmp[j++]=record[begin2++];
for(int i=begin;i<=end;i++)
record[i]=tmp[i-begin];
return ret;
}
};方式2：在左边选一个数，看右边哪个比他小
- 假设我们排的是升序：
假设此时nums[begin1]>nums[bgein2],此时右边 mid+1 到 begin2 之间的数都小于nums[begin1],就可以统计结果， begin2++后，仍然有可能 nums[begin1]>nums[bgein2] ，此时统计的结果就存在重复，所以方式2只能采用降序的方式
- 假设是降序
假设 nums[begin1]<=nums[bgein2] ，begin2就需要++，如果nums[begin1]>nums[bgein2] 的话，说明右边 begin2 到end之间的元素都小于nums[begin1],此时右边可以与nums[begin1]构成逆序对的数都统计出来了，begin1就可以++
class Solution {
int tmp[50010];
public:
int reversePairs(vector<int>& record) {
return MergeSort(record,0,record.size()-1);
}
int MergeSort(vector<int>& record,int begin,int end)
{
if(begin>=end) return 0;
int mid=(begin+end)/2;
int ret=0;
ret+=MergeSort(record,begin,mid);
ret+=MergeSort(record,mid+1,end);
//处理一左一右
int begin1=begin,end1=mid;
int begin2=mid+1,end2=end;
int j=0;
while(begin1<=end1&&begin2<=end2)
{
if(record[begin1]<=record[begin2])
{
tmp[j++]=record[begin2++];
}
else
{
ret+=(end-begin2+1);
tmp[j++]=record[begin1++];
}
}
while(begin1<=end1) tmp[j++]=record[begin1++];
while(begin2<=end2) tmp[j++]=record[begin2++];
for(int i=begin;i<=end;i++)
record[i]=tmp[i-begin];
return ret;
}
};二、计算右侧小于当前元素的个数
题目链接：
315. 计算右侧小于当前元素的个数 - 力扣（LeetCode）
题目介绍：
给你一个整数数组 nums ，按要求返回一个新数组 counts 。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。
1 <= nums.length <= 105-104 <= nums[i] <= 104
思路：
这个题目的思路完全和上一个题目一样，不同的地方是这个题要我们返回一个数组，数组的元素代表nums对应那个元素的逆序对个数，我们上面的思路实在归并排序的过程中计算出逆序对的，但是由于要排序，数组元素的对应位置也会改变，所以我们需要解决这个问题即可。
通过元素的值构建哈希表这个方案是不能用的，因为数组可能会有重复的元素，但是我们还是要利用哈希的原理，我们可以创建一个数组index，让这个数组映射nums每个元素的下标，在对nums排序时，连带index数组一起排序，这样映射关系就建立好了。
所以我们一共需要创建两个辅助数组，tmpNums、tmpIndex，一个用来辅助Nums排序，一个用来辅助index数组排序
class Solution {
public:
int tmpNums[500010];
int tmpIndex[500010];
vector<int> ret;
vector<int> index;
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 begin,int end)
{
if(begin>=end)return;
int mid=(begin+end)/2;
MergeSort(nums,begin,mid);
MergeSort(nums,mid+1,end);
int begin1=begin,end1=mid;
int begin2=mid+1,end2=end;
int j=0;
while(begin1<=end1&&begin2<=end2)
{
if(nums[begin1]<=nums[begin2])
{
tmpNums[j]=nums[begin2];
tmpIndex[j++]=index[begin2++];
}
else
{
ret[index[begin1]]+=(end2-begin2+1);
tmpNums[j]=nums[begin1];
tmpIndex[j++]=index[begin1++];
}
}
while(begin1<=end1)
{
tmpNums[j]=nums[begin1];
tmpIndex[j++]=index[begin1++];
}
while(begin2<=end2)
{
tmpNums[j]=nums[begin2];
tmpIndex[j++]=index[begin2++];
}
for (int i = begin; i <= end; i++) {
nums[i] = tmpNums[i - begin];
index[i] = tmpIndex[i - begin];
}
}
};三、翻转对
题目链接:
题目介绍:
给定一个数组 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个重要翻转对。
你需要返回给定数组中的重要翻转对的数量。
- 给定数组的长度不会超过
50000。 - 输入数组中的所有数字都在32位整数的表示范围内。
思路：
这个题目的思路与逆序对那个题目几乎一样，不同的是逆序对那个题找的是nums[i]>nums[j],与归并排序的判断一致，所以就一边合并一边计算了，但是这个题的判断是大于2倍，与归并排序的判断条件并不符合，如果硬要边和并边计算从理论上说是可以的，但是这样会增加程序的复杂度，所以我们需要在归并前，利用两边是有序的特性，计算出翻转对的个数。
假设我们是降序的，如果nuns[begin1] <= nums[begin2] *2的话，就让cur2++，如果
nuns[begin1] > nums[begin2]*2 的话，由于是降序，begin2到end之间的元素也是符合要求的，此时让begin1++，继续判断，这样指针没有回退，求翻转对的时间复杂度就是O（N）
class Solution {
int tmp[50010];
public:
int reversePairs(vector<int>& nums) {
return MergeSort(nums,0,nums.size()-1);
}
int MergeSort(vector<int>& nums,int begin,int end)
{
if(begin>=end) return 0;
int mid=(begin+end)/2;
int ret=0;
ret+=MergeSort(nums,begin,mid);
ret+=MergeSort(nums,mid+1,end);
//处理翻转对
int begin1=begin,end1=mid;
int begin2=mid+1,end2=end;
while(begin1<=end1)
{
while(begin2<=end2&&nums[begin2]>=nums[begin1]/2.0)
begin2++;
if(begin2>end2)break;
ret+=end-begin2+1;
begin1++;
}
//处理一左一右
begin1=begin,end1=mid;
begin2=mid+1,end2=end;
int j=0;
while(begin1<=end1&&begin2<=end2)
{
if(nums[begin1]<=nums[begin2])
{
tmp[j++]=nums[begin2++];
}
else
{
tmp[j++]=nums[begin1++];
}
}
while(begin1<=end1) tmp[j++]=nums[begin1++];
while(begin2<=end2) tmp[j++]=nums[begin2++];
for(int i=begin;i<=end;i++)
nums[i]=tmp[i-begin];
return ret;
}
};