当前位置：首页 > news >正文

【优选算法---归并排序衍生题目】剑指offer51---数组中的逆序对、计算右侧小于当前元素的个数、翻转对

news 来源：原创 2025/5/24 5:00:44

一、剑指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];}}
};

三、翻转对

题目链接:

493. 翻转对 - 力扣（LeetCode）

题目介绍:

给定一个数组 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;}
};

一、剑指offer51---数组中的逆序对

题目链接:

题目介绍：

思路：

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

题目链接：

题目介绍：

思路：

三、翻转对

题目链接:

题目介绍:

思路：

相关文章：