【分治】计算右侧小于当前元素的个数
【分治】计算右侧小于当前元素的个数
315. 计算右侧小于当前元素的个数
给你一个整数数组 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
解题思路：归并排序 + 辅助数组定位
这道题其实用到了前面讲的 剑指 Offer 51. 数组中的逆序对 这道题中的第二个思路，也就是找 比该值之后小的数，正好是符合该题意的，所以我们对于归并排序要使用 降序 才行！
这里直接贴出这个这种思路的做法，具体的细节可以参考逆序对那道题的笔记！假设原数组是 nums，则：
nums[cur1] <= nums[cur2]的话：- 直接让
nums[cur2]拷贝到临时数组中，并让cur2++即可！
- 直接让
nums[cur1] > nums[cur2]的话：- 可以得到
right - cur2 + 1就是比nums[cur1]小的后面区间的元素，然后将nums[cur1]拷贝到临时数组中，并让cur1++即可。
- 可以得到
这道题之所以还可以用分治的思想，就是因为分为左右区间之后，两个区间的元素虽然都排序了，但是左右区间的相对位置还是不变的，右区间的元素还是保持在左区间元素的后面，所以是符合题目要求的！
不过这道题细节需要修改一下，因为这道题要求的不是总数了，而是每个元素都要找到其后面小的数的个数，也就是说在归并的时候，我们要让原数组中对应元素都参与 nums[i] += right - cur2 + 1，但是问题来了，既然原数组 nums 要参与归并排序，那么一旦排序之后元素顺序就乱了，我们就 找不到当前计算出来的个数要累加到原数组中的哪个元素了，那该怎么办❓❓❓
可能一开始会想到的就是使用哈希表，然后让哈希表存放元素的值作为
key，元素的下标作为value，但是问题是有可能原数组中有重复的元素，此时问题就变得更加复杂了，我们还得去对每个元素搞一个标识符，这就很麻烦，所以我们要换个思路。
这里一个比较简单的思路就是再 创建一个辅助数组 index，用来存放的是原数组中每个元素对应的下标，如下图所示：
乍一看好像和哈希表的功能差不多，但是它做到哈希表做不到的一点，就是 当原数组 nums 排序之后，辅助数组 index 对应的位置也会跟着原数组 nums 变化，如下图所示：
也就是说，辅助数组 index 记录下来 nums 数组最原始的模样，虽然归并排序的过程中会跟着原数组 nums 对应的位置不断变化，但是其值对应的下标却是不变的，并且有重复元素也不怕，因为它们各自的下标都是不同的！
只不过我们要注意一个问题，既然原数组 nums 在归并排序的时候需要用到一个辅助数组 tmp1 来合并，那么我们用来记录下标的 辅助数组 index 也需要有一个辅助数组 tmp2 来合并，这就是所谓的空间换时间的方法！
剩下的细节，参考代码：
class Solution {
private:
vector<int> index; // 记录下标的辅助数组
vector<int> tmp1; // 用于原数组归并的辅助数组
vector<int> tmp2; // 用于辅助数组index归并的辅助数组
vector<int> count; // 用于返回最终结果的数组
public:
vector<int> countSmaller(vector<int>& nums) {
// 初始化辅助数组和结果数组
int n = nums.size();
tmp1.resize(n);
tmp2.resize(n);
count.resize(n);
// 初始化记录下标的辅助数组
for(int i = 0; i < n; ++i)
index.push_back(i);
merge_sort(nums, 0, n - 1);
return count;
}
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 = left;
while(cur1 <= mid && cur2 <= right)
{
if(nums[cur1] <= nums[cur2])
{
tmp1[i] = nums[cur2];
tmp2[i] = index[cur2]; // index数组对应的位置也跟着变化，但是值不变
i++;
cur2++;
}
else
{
count[index[cur1]] += right - cur2 + 1; // 重点：将计算的个数累加到结果集对应最初数组的位置
tmp1[i] = nums[cur1];
tmp2[i] = index[cur1]; // index数组对应的位置也跟着变化，但是值不变
i++;
cur1++;
}
}
// 处理剩下的排序过程
while(cur1 <= mid)
{
tmp1[i] = nums[cur1];
tmp2[i] = index[cur1]; // index数组对应的位置也跟着变化，但是值不变
i++;
cur1++;
}
while(cur2 <= right)
{
tmp1[i] = nums[cur2];
tmp2[i] = index[cur2]; // index数组对应的位置也跟着变化，但是值不变
i++;
cur2++;
}
// 拷贝回原来数组，完成归并
while(left <= right)
{
nums[left] = tmp1[left];
index[left] = tmp2[left];
left++;
}
}
};腾讯云开发者
