目录
归并排序非递归
如果不太了解非递归的老铁可以看一下我之前的博客，在这里给出归并排序第二种写法比之前的更加简洁：
我们实现非递归的时候是先分组在一组一组的合并。我们定义变量L指向左组的起始位置,定义变量M指向左组的末尾位置，定义变量R指向右组的末尾位置，定义mergeSize控制步长
一开始 1和0做为一组进行归并，归并完之后变成：
归并完成后L来到R+1位置合并新的一组R则来到mergize+M位置合并新的一组
重复上面的过程即可完成第一躺排序
此时已经有序但是我们不知道有序：进行第二躺合并：步长扩大两倍
但是当合并完这一趟之后L来到R+1的位置而R确不存在此时我们只需要将左组拷贝下来即可。或者当右组不够时我们任然将其和左组合并
对应代码：
void Merge(vector<int>& arr, int L, int M, int R) {//合并左组和右组 int begin1 = L; int end1 = M; int begin2 = M + 1; int end2 = R; int index = 0; vector<int>tmp(R - L + 1); while (begin1 <= end1 && begin2 <= end2) { tmp[index++] = arr[begin1] <= arr[begin2] ? arr[begin1++] : arr[begin2++]; } while (begin1 <= end1) { tmp[index++] = arr[begin1++]; } while (begin2 <= end2) { tmp[index++] = arr[begin2++]; } //拷贝回去 for (int i = 0; i < R - L + 1; i++) { arr[i + L] = tmp[i]; } } void MergeSort(vector<int>&arr) { int mergeSize = 1;//步长 int n = arr.size(); while (mergeSize < n) { int L = 0;//左组的开始 while (L < n) { int M = L + mergeSize - 1;//左组的右边界 if (M >= n) { break; } int R = min(M + mergeSize, n - 1);//右组的右边界这里取最小的原因是右组有可能不够 Merge(arr, L, M, R);//合并 L = R + 1;//移动L继续合并下一组 } if (mergeSize > n / 2) {//防止mergeSize过大溢出出现错误 break; } mergeSize <<= 1;//相当于mergeSize*=2; } }
2.计算小和问题
对应牛客网链接：
题目描述：
数组小和的定义如下：
\sum_{i=1}^{n} f_i \∑i=1nfi (其中 f _i\fi 的定义是第 i 个数的左侧小于等于 s_i\si 的个数)
例如，数组 s = [1, 3, 5, 2, 4, 6] ，在 s[0] 的左边小于或等于 s[0] 的数的和为 0 ； 在 s[1] 的左边小于或等于 s[1] 的数的和为 1 ；在 s[2] 的左边小于或等于 s[2] 的数的和为 1+3=4 ；在 s[3] 的左边小于或等于 s[3] 的数的和为 1 ；
在 s[4] 的左边小于或等于 s[4] 的数的和为 1+3+2=6 ；在 s[5] 的左边小于或等于 s[5] 的数的和为 1+3+5+2+4=15 。所以 s 的小和为 0+1+4+1+6+15=27
给定一个数组 s ，实现函数返回 s 的小和
第一行有一个整数N。表示数组长度
接下来一行N个整数表示数组内的数一个整数表示答案
输入：
6 1 3 5 2 4 6复制输出：
27复制
输入：
1 10
解题思路：
1.对于每个数，我们需要的是它左侧所有小于等于它的数之和。对于所有的数找到它的和。然后累加得到结果。
2.如果只看结果，我们可以发现，如果s[i]右边大于它的数有n个，那么这个数在最后的最后结果中的贡献就是n * s[i]。
对于这个数组我们来要求左边小于等于它的小和我们可以转换为右边大于等于它的小和
我们首先看这个数组归并的过程中
先看第一组，首先比较一开始的元素：显然3是大于2的那么就1个大于1的累加到答案里，在将1和3拷贝到临时数组里面
在看下一组：
同样的我们首先比较一开始的元素发现5大于2不产生小和，将2拷贝到临时数组里面然后begin2++就越界了，然后将5拷贝到临时数组里面begin1也就越界了,这次就结束了.然后就是4和6进行合并产生一个小和4
进行第二躺和并的时候：
同样的首先看一开始的元素的大小2是大于1的那么5也是大于1的产生两个小和1如何计算有多少个了？和简单拿右组的右边界-左边界+1就是的
，然后being1++到了3，3不大于2，beign2++不产生小和，而5此时大于3产生小和。
同理和并1 2 3 5 和 4 6的时候也如此。
注意：当左组==右组的时候先拷贝左组。这是因为你要求的是右组大于等于左组的个数
对应代码：
#include<iostream> #include<vector> using namespace std; long long merge(vector<int>&arr,int L,int M,int R){ long long ans=0; int begin1=L; int begin2=M+1; vector<int>tmp(R-L+1); int index=0; while(begin1<=M&&begin2<=R){ ans+=arr[begin1]<=arr[begin2]?(R-begin2+1)*arr[begin1]:0; tmp[index++]=arr[begin1]<=arr[begin2]?arr[begin1++]:arr[begin2++]; //相等先拷贝左组因为要我们没有办法确定右组大于左组的个数 } while(begin1<=M){ tmp[index++]=arr[begin1++]; } while(begin2<=R){ tmp[index++]=arr[begin2++]; } for(int i=0;i<tmp.size();i++){ arr[i+L]=tmp[i]; } return ans; } long long process(vector<int>&arr,int L,int R){ if(L==R){//只有一个数没有小和产生 return 0; } int mid=(L+R)>>1; //左组的小和+右组的小和+合并时产生的小和为最终的答案 return process(arr,L,mid)+process(arr, mid+1, R) +merge(arr, L, mid, R); } long long Getsum(vector<int>&arr){ return process(arr,0,arr.size()-1); } int main(){ int n; cin>>n; vector<int>arr(n); for(int i=0;i<n;i++){ cin>>arr[i]; } cout<<Getsum(arr); }
逆序对问题
对应letecode链接：
题目描述：
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
示例 1:
输入: [7,5,6,4]
输出: 5限制：
0 <= 数组长度 <= 50000
解题思路：
本题思路和上题基本一样，要求逆序对实质就是求右边有多少个数比前数小，我们就可以转化为左边有多少个数比右边大。
对应代码：
class Solution { public: int ret=0; int reversePairs(vector<int>& nums) { MergeSort(nums,0,nums.size()-1); return ret; } void MergeSort(vector<int>&nums,int L,int R){ if(L>=R)return; int M=(L+R)>>1; MergeSort(nums,L,M); MergeSort(nums,M+1,R); Merge(nums,L,M,R); } void Merge(vector<int>&nums,int L,int M,int R){ int p1=L; int p2=M+1; int index=0; vector<int>tmp(R-L+1); while(p1<=M&&p2<=R){ ret+=nums[p1]>nums[p2]?(M-p1+1):0; tmp[index++]=nums[p1]<=nums[p2]?nums[p1++]:nums[p2++];//相等先拷贝左边的 } while(p1<=M){ tmp[index++]=nums[p1++]; } while(p2<=R){ tmp[index++]=nums[p2++]; } for(int i=0;i<tmp.size();i++){ nums[i+L]=tmp[i]; } } };
下面我们再来看一题：
计算数组nums右边有多少个数乘2依然小于当前数
思路：和上面两题是一样都总个数=左组和右组的个数+合并过程中产生的个数
定义一个指针指向左组的开始定义一个指针指向右组的开始从右组中计算满足条件的个数，计算完成之后再合并两个数组
对应代码：
int merge(vector<int>& nums, int L, int M, int R) { int ans = 0; int windowR = M + 1;//先计算 for (int i = L; i <= M; i++) { while (windowR <= R && nums[i] > nums[windowR] * 2) { windowR++; } ans += windowR - M - 1; } //合并 int begin1 = L; int begin2 = M + 1; int index = 0; vector<int>tmp(R - L + 1); while (begin1 <= M && begin2 <= R) { tmp[index++] = nums[begin1] < nums[begin2] ? nums[begin1++] : nums[begin2++]; } while (begin1 <= M) { tmp[index++] = nums[begin1++]; } while (begin2 <= R) { tmp[index++] = nums[begin2++]; } for (int i = 0; i < tmp.size(); i++) { nums[i + L] = tmp[i]; } return ans; } int process(vector<int>& nums, int L, int R) { if (L == R) { return 0; } int mid = (L + R) >> 1; return process(nums, L, mid) + process(nums, mid + 1, R) + merge(nums, L, mid, R); } int biggerTwice(vector<int>& nums) { return process(nums, 0, nums.size() - 1); } int main() { int n; cin >> n; vector<int>tmp(n); for (int i = 0; i < n; i++) { cin >> tmp[i]; } cout << biggerTwice(tmp); }
计算右侧小于当前数的数量
对应letecode链接：
题目描述：
给你一个整数数组 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 个更小的元素
示例 2：输入：nums = [-1]
输出：[0]
示例 3：输入：nums = [-1,-1]
输出：[0,0]
提示：
1 <= nums.length <= 105
-104 <= nums[i] <= 104
本题思路：
本题思路与上面的题有一点点的区别由于题目要我们返回的是一个数组，因此我们需要将数组的值和下表绑定在一起。在归并的过程中我们从左组和右组的右边开始合并，如果右组小于左组的话直接根据下标计算数量，如果左组小于右组，右组往后移动，注意如果相等的话先拷贝右组。
对应代码：
class Solution { public: class Node{//数组中的每一个值和其下标 public: Node(int v=0,int i=0) :val(v) ,index(i) {} int val; int index; }; vector<int> countSmaller(vector<int>& nums) { vector<int>ans(nums.size()); if(nums.size()<2){ return ans; } vector<Node*>arr(nums.size());//存储每个值所对应的小标 for(int i=0;i<nums.size();i++){ arr[i]=new Node(nums[i],i); } process(arr,0,arr.size()-1,ans); return ans; } void process(vector<Node*>&arr,int L,int R,vector<int>&ans){ if(L==R){ return; } int mid=(L+R)>>1; process(arr,L,mid,ans); process(arr,mid+1,R,ans); merge(arr,L,mid,R,ans); } //合并 void merge(vector<Node*>&arr,int L,int M,int R,vector<int>& ans){ vector<Node*>tmp(R-L+1); int index=tmp.size()-1; int end1=M; int end2=R;//从往左合并 while(end1>=L&&end2>=M+1){ if(arr[end1]->val>arr[end2]->val){ ans[arr[end1]->index]+=end2-M; } tmp[index--]=arr[end1]->val>arr[end2]->val?arr[end1--]:arr[end2--]; } while(end1>=L){ tmp[index--]=arr[end1--]; } while(end2>=M+1){ tmp[index--]=arr[end2--]; } //拷回原数组 for(int i=0;i<tmp.size();i++){ arr[L+i]=tmp[i]; } } };
区间和的个数
对应letecode链接：
题目描述：
给你一个整数数组 nums 以及两个整数 lower 和 upper 。求数组中，值位于范围 [lower, upper] （包含 lower 和 upper）之内的 区间和的个数 。
区间和 S(i, j) 表示在 nums 中，位置从 i 到 j 的元素之和，包含 i 和 j (i ≤ j)。
示例 1：
输入：nums = [-2,5,-1], lower = -2, upper = 2
输出：3
解释：存在三个区间：[0,0]、[2,2] 和 [0,2] ，对应的区间和分别是：-2 、-1 、2 。
示例 2：输入：nums = [0], lower = 0, upper = 0
输出：1
提示：
1 <= nums.length <= 105
-231 <= nums[i] <= 231 - 1
-105 <= lower <= upper <= 105
题目数据保证答案是一个 32 位 的整数
解题思路：
我们先来了解一下如和快速的求解数组中i到j范围内的累加和：
如果调用非常的频繁我们每次暴力去取时间复杂度为O(N^2).其实我们可以利用一个累加和数组sum,sum[i]的含义是从0累加到i位置的和。这样我们求i到j位置的累加和就是sum[j]-sum[i]即可
我们要求数组中所有子数组中的累加和在一个范围上。我们假设0到i的累加和为x,范围为[lower,up]我们要求必须以i位置结尾的子数组目标有多少个在[lower,upper]上就等等同于求去求i之前有多少个累加和在[x-upper,x-lower]上。这是为什么了？举个例子
我们假设0到10位置的累加和为100，范围为[10,40]，此时[x-upper,x-lower]为[60,90]
我们假设0到0范围内的累加和为40不在[60,90]之间，那么也就意味着[1到10】的累加和为60不在题目要求的[10,40]之间。如果0到0的累加和为60在[60,90]之间，对应1到10到累加和为40在[10.40]之间。那么如和快速求出答案了？当然是归并排序的merge过程。我们在merge的过程中让右组的每一个数作为子数组的结尾，在判断左组有多少个数在[x-upper,x-lower]上
，由于左组和右组是有序的所以x-upper和x-lower是递增的符合滑动窗口的特性，因此我们可以用窗口来求个数，详细请看代码
对应代码：
class Solution { public: int countRangeSum(vector<int>& nums, int lower, int upper) { vector<long long >sum(nums.size()); sum[0]=nums[0]; for(int i=1;i<nums.size();i++){ sum[i]=sum[i-1]+nums[i];//获取前缀和数组 } return process(sum,0,sum.size()-1,lower,upper); } int process(vector<long long >&sum,int L,int R,int lower,int upper){ if(L==R){ //此处是指对应到nums数组中0到L的累加和是否满足条件 return sum[L]>=lower&&sum[L]<=upper?1:0; } int mid=(L+R)>>1; //左边的加上右边的在加上合并过程中的即为总答案 return process(sum,L,mid,lower,upper)+process(sum,mid+1,R,lower,upper)+merge(sum,L,mid,R,lower,upper); } int merge(vector<long long >&arr,int L,int M,int R,int lower,int upper){ int ans=0; int windowL=L; int windowR=L;//先计算有多少个数落在这个范围上 for(int i=M+1;i<=R;i++){ long long Min=arr[i]-upper; long long Max=arr[i]-lower; while(windowR<=M&&arr[windowR]<=Max){//小于区间的右边界 windowR++;//找到满足条件的左边界 } while(windowL<=M&&arr[windowL]<Min){//找到子数组满足条件的右边界 windowL++; } ans+=windowR-windowL; } //防止windowL和windowR错开即没有数在范围内 //下面是合并过程 vector<long long >tmp(R-L+1); int index=0; int begin1=L; int begin2=M+1; while(begin1<=M&&begin2<=R){ tmp[index++]=arr[begin1]<=arr[begin2]?arr[begin1++]:arr[begin2++]; } while(begin1<=M){ tmp[index++]=arr[begin1++]; } while(begin2<=R){ tmp[index++]=arr[begin2++]; } for(int i=0;i<tmp.size();i++){ arr[i+L]=tmp[i]; } return ans; } };