算法2(C++实现)

这篇博客我们将介绍前缀和，位运算，分治三种算法。

4. 前缀和

前缀和可以用来解决连续子数组中的一些问题，或者当题目出现前缀后缀的字眼也可以用它解决，前缀和问题在解决过程中是通过一边遍历前缀和数组（或原数组），一边更新结果去解决；同时前缀和是一种思想，并不一定非得构建一个前缀和数组，有时使用hash表也可以替代。

一维前缀和：

a. 先预处理出来⼀个前缀和数组：用dp[i] 表示： [0, i-1] 区间内所有元素的和，初始化dp[0]=arr[0],可得递推公式： dp[i] = dp[i-1] +arr[i]；

b. 使用前缀和数组，快速求出某⼀个区间内所有元素的和：当询问的区间是[l, r] 时：区间内所有元素的和为： dp[r] - dp[l - 1] 。

二维前缀和：类⽐于⼀维数组的形式，如果我们能处理出来从[0, 0] 位置到[i, j] 位置这⽚区域内所有元素的累加和，就可以在O(1) 的时间内，搞定矩阵内任意区域内所有元素的累加和。因此我们

接下来仅需完成两步即可：

第⼀步：搞出来前缀和矩阵

这⾥就要⽤到⼀维数组⾥⾯的拓展知识，我们要在矩阵的最上⾯和最左边添加上⼀⾏和⼀列 0，（vector<vector<int>> dp(m + 1, vector<int>(n + 1));）这样我们就可以省去⾮常多的边界条件的处理。此后我们要注意前缀和数组dp[i][j]和arr[i][j]的映射关系，映射时 arr中i和j都要减一

a. dp[i][j] 的含义：dp[i][j] 表⽰，从 [0, 0] 位置到 [i, j] 位置这段区域内，所有元素的累加和。递推⽅程就是：dp[i][j]=dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1]+arr[i-1][j-1]    （arr[i-1][j-1]是因为映射关系)

第二步：使用前缀和矩阵

从（row1，col1）到（row2，col2）的元素和为dp[row2][col2]-dp[row1-1][col2]-dp[row2][col1-1]+dp[rowl-1][col1-1]

4.1  238. 除自身以外数组的乘积 - 力扣（LeetCode）

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内。

请 不要使用除法，且在 O(n) 时间复杂度内完成此题。

示例 1:

输入: nums = [1,2,3,4]
输出: [24,12,8,6]

解法：可知ans[i]=num[0]*num[1]*....num[i-1] (前缀积)   *    num[i+1]*num[i+2]...num[n]（后缀积），因此该题需要预处理两个数组，然后将该位置前一个位置的前缀和乘以后一个位置的后缀和即可得到answer。

class Solution {
public:
// 分析题意可知ans[i]=num[0]*num[1]*....num[i-1] (前缀和)*num[i+1]*num[i+2]...num[n]vector<int> productExceptSelf(vector<int>& nums) {//使用一个数组存储前缀积int n=nums.size();//需要多开辟一个位置，因为需要这个位置前一个地方的post[i]int* post=new int[n+1];post[0]=1;for(int i=1;i<n;i++){post[i]=post[i-1]*nums[i-1];}//使用一个数组存储后缀积int* dp=new int[n+1];dp[n]=1;for(int i=n-1;i>=0;i--){dp[i]=dp[i+1]*nums[i];}vector<int>  ret;ret.resize(n);cout<<dp[1]<<post[1];for(int i=0;i<n;i++){ret[i]=post[i]*dp[i+1];}return ret;}
};

4.2 560. 和为 K 的子数组 - 力扣（LeetCode）

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

子数组是数组中元素的连续非空序列。

示例 1：

输入：nums = [1,1,1], k = 2
输出：2

思路：设 i 为数组中的任意位置，要统计和为k的子数组的个数，只需要统计在这个位置前面有多少个前缀和为 sum[i]-k的位置，我们仅需⽤⼀个哈希表，⼀边求当前位置的前缀和，⼀边存下之前每⼀种前缀和出现的次数。

class Solution {
public:int subarraySum(vector<int>& nums, int k) {unordered_map<int,int> hash;hash[0]=1;int sum=0,ret=0;for(auto x:nums){sum+=x;if(hash.count(sum-k)) ret+=hash[sum-k];hash[sum]++;}return ret;}
};

4.3 974. 和可被 K 整除的子数组 - 力扣（LeetCode）

给定一个整数数组 nums 和一个整数 k ，返回其中元素之和可被 k 整除的非空 子数组 的数目。

子数组 是数组中 连续 的部分。

示例 1：

输入：nums = [4,5,0,-2,-3,1], k = 5
输出：7
解释：
有 7 个子数组满足其元素之和可被 k = 5 整除：
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

该题目与上个题目类似。求解该题目我们还需要两个知识点。

1.(a-b)%k=0,只需要a%k等于b%k即可

2.C++中负数对正数区模，是把负号放在一边，进行正数部分相模，在加负号，如：

-1%3=-（1%3）=-1，但是根据题意我们希望得到2，因此我们取模运算可以变成(k+n%k)%k,

极为（3+（-1））%3=2.

思路：前缀和，我们要求解以任意一个位置i结尾符合被k整除的子数组数目，只需要其前面位置x到i的和为k的整数倍，即[x,i]的和可被k整除，而由知识点1，我们可以知道当sum%k等于[0,x]的和模k，那么[x,i]的和可被k整除。

class Solution {
public://hash表中存储sum%k即可，C++取模得到的是负数，因此(a % n + n) % n的形式int subarraysDivByK(vector<int>& nums, int k) {unordered_map<int,int> hash;hash[0%k]=1;int sum=0;int ret=0;for(auto x:nums){sum+=x;int r=(sum%k+k)%k;if(hash.count(r)) ret+=hash[r];hash[r]++;}return ret;}
};

4.4 525. 连续数组 - 力扣（LeetCode）

给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。

示例 1:

输入: nums = [0,1]
输出: 2
说明: [0, 1] 是具有相同数量 0 和 1 的最长连续子数组。

思路：出现最长连续子数组，使用前缀和求解，这个题目思路比较巧妙，关键是以下三点：

1. 我们可以将0换成-1去算前缀和，因此问题变成和为0的最长子数组的长度

2. hash表中我们key放前缀和，而value我们存放它的位置，这样我们便可以统计这个区间的长度。

3.我们是从左往右找第一个前缀和等于sum的位置，因此后面再出现前缀和等于sum的元素，则它不进入hash表

class Solution {
public:int findMaxLength(vector<int>& nums) {unordered_map<int,int> hash;hash[0]=-1;  //默认存在一个和为0的情况，其下标为-1int ret=0;int sum=0;for(int i=0;i<nums.size();i++){sum+=nums[i]==0?-1:1;if(hash.count(sum)) ret=max(ret,i-hash[sum]);else hash[sum]=i;}return ret;}
};

4.5 1314. 矩阵区域和 - 力扣（LeetCode）

给你一个 m x n 的矩阵 mat 和一个整数 k ，请你返回一个矩阵 answer ，其中每个 answer[i][j] 是所有满足下述条件的元素 mat[r][c] 的和： 

• i - k <= r <= i + k,
• j - k <= c <= j + k 且
• (r, c) 在矩阵内。

示例 1：

输入：mat = [[1,2,3],[4,5,6],[7,8,9]], k = 1
输出：[[12,21,16],[27,45,33],[24,39,28]]

这个题目就是一个标准的二维前缀和的题目，但是它存在一个整数k，因此我们需要进行边界的讨论和取值，确定其是计算哪一部分区域的前缀和，我们之前说过，构建二维前缀和数组需要多构建一行和一列。此时使用前缀和数组时应当注意对应关系，本题还涉及边界情况的处理，因此我们在使用时讨论x1，x2，y1,y2的取值。

class Solution {
public:vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {int m=mat.size();int n=mat[0].size();//初始化一个dp数组vector<vector<int>> dp(m+1,vector<int>(n+1));for(int i=1;i<m+1;i++){for(int j=1;j<n+1;j++){dp[i][j]=dp[i-1][j]+dp[i][j-1]+mat[i-1][j-1]-dp[i-1][j-1];}}//使用dp数组vector<vector<int>> answer(m,vector<int>(n,0));for(int i=0;i<m;i++){for(int j=0;j<n;j++){int x1 = max(0, i - k) + 1, y1 = max(0, j - k) + 1;int x2 = min(m - 1, i + k) + 1, y2 = min(n - 1, j + k) + 1;answer[i][j] = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] +dp[x1 - 1][y1 - 1];}}return answer;}
};

5.位运算

5.1 基础位运算总结

<< >> ~  & | ^

给一个数字n，确定它的二进制表示第x位是0还是1：（n>>x）&1

给一个数字n，确定它的二进制表示第x位修改成1：n=n|(1<<x)或者：n=n^(1<<x)

提取一个数字n最右侧的1 ： n&(-n) 这是lowbit操作

将一个数字n最右侧的1变成0：n&(n-1)

位图的思想：

类似于一个hash数组，数组的每一处存储的不同值有着相关信息，位图则利用一个32位置的 int，它的每一个bit位都存储着相关信息

异或^ 考察最多（5.3 5.4 5.5 5.6），a^0=a  , a^a=0,  a^b^c=a^(b^c)

关于位图优先级，一定要多加括号（）,位运算的题目，可以将所给数字的32位bit表示给出了，观察特征，再选用位运算符即可。

5.2 面试题 01.01. 判定字符是否唯一 - 力扣（LeetCode）

实现一个算法，确定一个字符串 s 的所有字符是否全都不同。

示例 1：

输入: s = "leetcode"
输出: false 

• s[i]仅包含小写字母
• 如果你不使用额外的数据结构，会很加分。

该题最直接思路是用hash表做，但是考虑提示的两点，小写字母是在26位，直接使用一个整形即可表示，因此我们可以用int的每一个位置表示其对应字母是否出现过。

class Solution {
public:bool isUnique(string astr) {// 利⽤鸽巢原理来做的优化if(astr.size() > 26) return false;int a=0;for (auto x:astr){int n=x-'a';  //第n位if(((a>>n)&1)==0){a^=1<<n;}else{return false;}}return true;}
};

5.3 268. 丢失的数字 - 力扣（LeetCode）

给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。

示例 1：

输入：nums = [3,0,1]
输出：2
解释：n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 nums 中。

如果我们把数组中的所有数，以及 [0, n] 中的所有数全部「异或」在⼀起，那么根据「异或」运算的「消消乐」规律，最终的异或结果应该就是缺失的数~

class Solution {
public:int missingNumber(vector<int>& nums) {int ret=0;for(int i=0;i<=nums.size();i++) ret^=i;for(auto x:nums) ret^=x;return ret;}
};

5.4  371. 两整数之和 - 力扣（LeetCode）

给你两个整数 a 和 b ，不使用 运算符 + 和 - ，计算并返回两整数之和。

示例 1：

输入：a = 1, b = 2
输出：3

算法思路：

◦ 异或 ^ 运算本质是「⽆进位加法」；

◦ 按位与 & 操作能够得到「进位」；

◦ 然后⼀直循环进⾏，直到「进位」变成 0 为止。

我们可以让两个数a,b直接异或，那么最终结果就是每个 位置在无进位下的结果，之后我们再将进位结果carry左移一位，将无进位下的结果与进位的值再次相加即可，直到进位为0.

class Solution {
public:int getSum(int a, int b) {int ret=0;int carry=0;while(b!=0){ret=a^b;carry=(a&b)<<1;  //进位后的结果a=ret;b=carry;}return a;}
};

5.5 137. 只出现一次的数字 II - 力扣（LeetCode）

给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。

示例 1：

输入：nums = [2,2,3,2]
输出：3

思路：设要找的数位ret 。由于整个数组中，需要找的元素只出现了⼀次，其余的数都出现的三次，因此我们可以根据所有数的某⼀个比特位的总和%3 的结果，快速定位到ret 的⼀个比特位上的值是 0 还是 1 。这样，我们通过ret 的每⼀个⽐特位上的值，就可以将ret给还原出来

class Solution {
public:int singleNumber(vector<int>& nums) {// 考虑二进制表示，统计二进制1的出现次数，对3求余int cnt[32]={0};for(int i=0;i<nums.size();i++){// nums[i]即为数字//如果这一位为0，则对应加1，从第0位置开始for(int m=0;m<32;m++){if((nums[i]>>m)&1==1){cnt[m]++;}}}int ret=0;// cnt[32]中就是存储着这个数字for(int n=0;n<32;n++){cnt[n]%=3;if(cnt[n]==1){ret|=(1<<n);  //将ret对应位置的0变成1}}return ret;}
};

6.分治

我们分为快速排序算法的分治和归并排序算法的分治来介绍分治算法，先介绍快速排序算法中的分治。快速排序有点类似于二叉树的先序遍历法，先处理某个元素，再处理左右，而归并排序类似二叉树的后序遍历法，先不断分，直到不能再分，再进行有序数组的归并。

6.1 75. 颜色分类 - 力扣（LeetCode）

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地 对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库内置的 sort 函数的情况下解决这个问题。

示例 1：

输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]

思路：类比我们算法系列的第一题移动0，我们可以采取一个三指针方案，其中i指针遍历数组，将0向开始位置甩，2向最后位置甩，使得left指针左边全为0，right指针右边全为2。

class Solution {
public:void sortColors(vector<int>& nums) {int i=0;int left=-1;int n=nums.size();int right=n;//  划分为 0  1 2三个区间  left左边都是0，right右边都是2while(i<right){if(nums[i]==0){swap(nums[++left],nums[i]);i++;}else if(nums[i]==1){i++;}else{swap(nums[--right],nums[i]); //不需要++i，此时交换过来的元素没有被处理}}}
};

6.2 912. 排序数组 - 力扣（LeetCode）

先讲讲最经典的霍尔版本的快速排序，其思想是每次将大于num[pivot] 放到数组后面，小于num[pivot] 的值放到数组前面，将num[pivot] 排到它最终的位置，然后递归的排序该元素 num[pivot] 的左边区间与右边区间。它一定是相遇停止，右边指针先走，交换左右所指的值，最后出循环结束，将左右指针相遇位置的值与 num[pivot]交换。

int part_sort(vector<int>& nums,int left,int right){int pivot=left;cout<<nums[pivot]<<" ";//霍尔方法while(left<right){while(left<right&&nums[right]>=nums[pivot]){right--;}while(left<right&&nums[left]<=nums[pivot]){left++;}swap(nums[left],nums[right]);}swap(nums[pivot],nums[left]);return left;}void quick_sort (vector<int>& nums,int begin,int end){if(begin>=end){return ;}int partion = part_sort(nums,begin,end);quick_sort(nums,begin,partion-1);quick_sort(nums,partion+1,end);}vector<int> sortArray(vector<int>& nums) {int begin=0;int end=nums.size()-1;quick_sort(nums,begin,end);return nums;}

以上代码在数组有序时去排序会超时，同时如果数据含有大量重复元素时也会超时。

因此我们优化1，随机选择基准元素pivot，pivot=rand()%(right-left+1)+left 2.采用数组分三块的思想，每次就可以排好所有值位nums[pivot]的元素。

 // 使用数组分三块实现快排  nums[i]pair<int,int> part_sort(vector<int>& nums,int left,int right){int r= rand() % (right - left + 1) + left;   //概率算期望，随机选择值可以解决O(Nlog(N))// 模上一个区间长度加初始下标int key=nums[r];int i=left;int left_partition=left-1;int right_partition=right+1;while(i<right_partition){if(nums[i]<key){swap(nums[i++],nums[++left_partition]);  //小于key的元素向前面甩}else if(nums[i]==key){i++;}else{swap(nums[i],nums[--right_partition]); //大于key的元素向后面甩}}return {left_partition,right_partition};  // //这两个位置一个是小于key，一个大于key，都需要处理}void quick_sort (vector<int>& nums,int begin,int end){if(begin>=end){return ;}pair<int,int> partion = part_sort(nums,begin,end);quick_sort(nums,begin,partion.first);quick_sort(nums,partion.second,end);}vector<int> sortArray(vector<int>& nums) {srand(time(NULL));int begin=0;int end=nums.size()-1;quick_sort(nums,begin,end);return nums;}

6.3 215. 数组中的第K个最大元素 - 力扣（LeetCode）

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:

输入: [3,2,1,5,6,4], k = 2
输出: 5

解法1：优先级队列。建立一个k个元素的小堆，其第一个元素一定最小，如果新进元素比它大，则入堆，返回这个堆顶元素，它就是最k大，同时她可以保证堆中的k个元素就是整个数组中前k大的。

int findKthLargest(vector<int>& nums, int k) {// 堆排序priority_queue<int,vector<int>,greater<int>> pq;for(int i=0;i<k;i++){pq.push(nums[i]);}for(int i=k;i<nums.size();i++){if(nums[i]>pq.top()){pq.pop();pq.push(nums[i]);}}return pq.top();
}

快速选择算法：在快排中，当我们把数组分成三块之后： [l, left] [left + 1, right - 1]，[right, r] ，我们可以通过计算每⼀个区间内元素的个数，进而推断出我们要找的元素是在哪⼀个区间里面。

我们随机选取区间内的一个key，用数组分三块的思想，将大于它的元素甩到区间后面，记大于key的元素区间长度为c,将小于它的元素甩到区间前面，记等key的元素区间长度为b,根据b，c与k的大小判断去相应的区间找最终结果key。

class Solution {
public:int findKthLargest(vector<int>& nums, int k) {srand(time(NULL));return quick_select(nums,0,nums.size()-1,k);}int quick_select(vector<int>&nums,int begin,int end,int k){if(begin>=end)return nums[begin];int left=begin-1;int right=end+1;int i=begin;int r=rand()%(end-begin+1)+begin;int key=nums[r];while(i<right){if(nums[i]<key){swap(nums[i++],nums[++left]);}else if(nums[i]==key){i++;}else{swap(nums[i],nums[--right]);}}if(end-right+1>=k){return quick_select(nums,right,end,k);}else if(end-left>=k){return key;}else{return quick_select(nums,begin,left,k-(end-left));}}
};

6.4 LCR 159. 库存管理 III - 力扣（LeetCode）

思路同上一道题，但是分治条件的处理有所不同，我们计算出数组第一块的长度，将它与k值对比，计算出a+b的长度与k值对比，最后的结果再做对应的处理。

class Solution {
public:vector<int> inventoryManagement(vector<int>& stock, int cnt) {// if(cnt==0)// return {};// priority_queue<int> pq;// for(int i=0;i<cnt;i++)// {//     pq.push(stock[i]);// }// int n=stock.size();// for(int i=pq.size();i<n;i++)// {//     if(stock[i]<pq.top())//     {//         pq.pop();//         pq.push(stock[i]);//     }// }// vector<int> ret;// while(!pq.empty())// {//     ret.push_back(pq.top());//     pq.pop();// }// return ret;//  快速选择srand(time(NULL));qsort(stock,0,stock.size()-1,cnt);//改变数组，使得数组的最前面的k个数即为最小的k个数return {stock.begin(),stock.begin()+cnt}; //迭代器区间构造}void qsort(vector<int>& nums, int begin,int end,int k){if(begin>=end){return;}int left=begin-1;int right=end+1;int i=begin;int r=rand()%(end-begin+1)+begin;int key=nums[r];while(i<right){if(nums[i]<key) swap(nums[i++],nums[++left]);else if(nums[i]==key) i++;else swap(nums[i],nums[--right]);}int a=left-begin+1;int b=right-left-1;if(a>k) qsort(nums, begin, left, k);  //判断前面小于key的区间是否 大于要求的数字kelse if(a + b >= k) return;     // 如果数组第一块长度小于k且数组前两块大于k，则返回else qsort(nums, right, end, k-a-b);}
};

6.5 912. 排序数组 - 力扣（LeetCode）

给你一个整数数组 nums，请你将该数组升序排列。

你必须在 不使用任何内置函数 的情况下解决问题，时间复杂度为 O(nlog(n))，并且空间复杂度尽可能小。

示例 1：

输入：nums = [5,2,3,1]
输出：[1,2,3,5]

思路：分治法

⼤体过程分为两步：

◦分：将数组⼀分为⼆为两部分，⼀直分解到数组的长度为1 ，使整个数组的排序过程被分为

「左半部分排序」+「右半部分排序」；

◦ 治：将两个较短的「有序数组合并成⼀个长的有序数组」，⼀直合并到最初的长度。

class Solution {void merge_sort(vector<int>& nums,int begin,int end){if(begin>=end)return;int mid=(end-begin+1)/2+begin;merge_sort(nums,begin,mid-1);  //每次排序时候，从begin开始merge_sort(nums,mid,end);//合并两个有序数组int i=begin;int j=mid;int k=0;int len=end-begin+1;while(i<=mid-1&&j<=end){if(nums[i]<nums[j]){tmp[k++]=nums[i++];}else{tmp[k++]=nums[j++];}}while(i<=mid-1){tmp[k++]=nums[i++];}while(j<=end){tmp[k++]=nums[j++];}for(i=0;i<len;i++){nums[begin+i]=tmp[i];}}public:vector<int> tmp;vector<int> sortArray(vector<int>& nums) {int n=nums.size();tmp.resize(n);merge_sort(nums,0,n-1);return nums;}
};

6.6 LCR 170. 交易逆序对的总数 - 力扣（LeetCode）

在股票交易中，如果前一天的股价高于后一天的股价，则可以认为存在一个「交易逆序对」。请设计一个程序，输入一段时间内的股票交易记录 record，返回其中存在的「交易逆序对」总数。

示例 1:

输入：record = [9, 7, 5, 4, 6]
输出：8
解释：交易中的逆序对为 (9, 7), (9, 5), (9, 4), (9, 6), (7, 5), (7, 4), (7, 6), (5, 4)。

思路：分治法，先分为一个个小数组，直到数组长度为1，合并的过程中，我们如何治？？这个问题关键在于加入我们排降序（此题目也可以排升序），如果cur2指向的元素小于cur1，则cur2后面所有元素都小于cur1，我们可以把他加入到ret中，返回ret即可

class Solution {
public:vector<int> tmp;int reversePairs(vector<int>& record) {//  7  5  6  4  a+b+c  左边+右边 +排序+ 一左一右   统计一左一右int ret=0;tmp.resize(record.size());merge_sort(record,0,record.size()-1,ret);return ret;}// 找这个数之前有多少数比我大（升序） ，  或者找这个数之后有多少数比我小（降序）void merge_sort(vector<int>& nums,int left,int right,int& ret){if(left>=right){return;}int mid=(left+right)>>1;merge_sort(nums,left,mid,ret);merge_sort(nums,mid+1,right,ret);int cur1=left,cur2=mid+1,i=0;while(cur1<=mid&&cur2<=right){//排降序   //如果排列升序，有另外写法if(nums[cur1]>nums[cur2]){ret+=(right-cur2+1);tmp[i++]=nums[cur1++];}else{//ret+=(mid-cur1+1);tmp[i++]=nums[cur2++];}}//剩余值只需要拷贝即可while(cur1<=mid){tmp[i++]=nums[cur1++];}while(cur2<=right){tmp[i++]=nums[cur2++];}for(i=left;i<=right;i++){nums[i]=tmp[i-left];}}
};

6.6 315. 计算右侧小于当前元素的个数 - 力扣（LeetCode）

给你一个整数数组 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 个更小的元素

思路：这⼀道题的解法与上一题求数组中的逆序对的解法是类似的，但是这⼀道题要求的不是求总的个数，而是要返回⼀个数组，记录每⼀个元素的右边有多少个元素比自己小。但是在我们归并排序的过程中，元素的下标是会跟着变化的，因此我们需要⼀个辅助数组，来将数组元素和对应的下标绑定在⼀起归并，也就是再归并元素的时候，顺势将下标也转移到对应的位置上。我们要快速统计出某⼀个元素后面有多少个比它小的，采用排降序，自己画图理解，升序可以统计左边有多少元素比自己大，因此升序很不好做。

class Solution {
public:// 只能排列降序//vector<int> tmp;vector<int> ret;vector<int> index;// vector<int> tmpindex;int tmp[500010];int tmpindex[500010];vector<int> countSmaller(vector<int>& nums) {//tmp.resize(nums.size());int n=nums.size();ret.resize(n);index.resize(n);//tmpindex.resize(nums.size());for(int i=0;i<nums.size();i++){index[i]=i;} merge_sort(nums,0,n-1);return ret;}void merge_sort(vector<int>& nums,int left,int right){if(left>=right){return ;}int mid=(left+right)>>1;merge_sort(nums,left,mid);merge_sort(nums,mid+1,right);int cur1=left,cur2=mid+1,i=0;while(cur1<=mid&&cur2<=right){if(nums[cur1] <= nums[cur2]){tmp[i] = nums[cur2];tmpindex[i++] = index[cur2++];}else{ret[index[cur1]] += right - cur2 + 1; // 不用index找到下表则无法知道哪个位置ret[i]加tmp[i] = nums[cur1];tmpindex[i++] = index[cur1++];}}while(cur1 <= mid){tmp[i] = nums[cur1];tmpindex[i++] = index[cur1++];}while(cur2 <= right){tmp[i] = nums[cur2];tmpindex[i++] = index[cur2++];}for(i=left;i<=right;i++){nums[i]=tmp[i-left];index[i] =tmpindex[i-left];}}
};