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