【算法】分治：归并排序之 315.计算右侧小于当前元素的个数（hard）

给你一个整数数组 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

3、解法

题解 - 力扣（LeetCode）

在这里推荐大家阅读上面这篇题解~

大概能清楚大部分思路。

具体步骤如下：

1. 初始化：创建一个与原数组 nums 大小相同的 index 数组，用于存储 nums 中每个元素的原始索引。

   1. 这是因为归并排序会打乱元素的顺序，但我们需要保留元素的原始位置来正确计算每个位置的结果。同时，创建两个辅助数组 index_temp 和 ret，其中 index_temp 用于归并过程中的临时索引存储，ret 用于存储最终结果，即每个元素右侧小于它的元素数量。

2. 归并排序：对 nums 数组进行归并排序，但在排序过程中，我们并不直接对 nums 进行操作，而是对 index 数组进行操作。这样做的原因是，我们可以通过 index 数组间接地比较 nums 中的元素，并保留元素的原始位置信息。在归并的过程中，每当我们将一个来自左子数组的索引放入 index_temp 时，我们就知道它右侧（在 nums 中）有多少来自右子数组的元素小于它（这些元素已经被排序并放在其右侧），从而可以更新 ret 数组中对应位置的值。

3. 计算并更新结果：在归并的过程中，我们使用两个指针 i 和 j 分别指向左子数组和右子数组的当前索引，并通过比较 nums[index[i]] 和 nums[index[j]] 的大小来决定将哪个索引放入 index_temp。

   1. 如果 nums[index[i]] 小于或等于 nums[index[j]]，那么我们可以安全地将 index[i] 放入 index_temp，并增加 ret[index[i]] 的值，增加的数量是 j - mid - 1（即当前右子数组中还未处理的、且小于 nums[index[i]] 的元素数量）。

4. 返回结果：归并排序完成后，ret 数组中存储的就是每个元素右侧小于它的元素数量，直接返回 ret 即可。

这种方法的时间复杂度是 O(n log n)，因为归并排序的时间复杂度是 O(n log n)，而我们在归并的过程中只进行了线性的额外操作。空间复杂度也是 O(n)，因为我们使用了与输入数组大小相同的额外空间来存储索引、临时索引和结果。

4、代码 

class Solution {
public:vector<int> index_temp;vector<int> ret;void mergeSort(vector<int>& nums, vector<int>& index, int l, int r) {if (l >= r) return;int mid = (l + r) >> 1;mergeSort(nums, index, l, mid);mergeSort(nums, index, mid + 1, r);if (nums[index[mid]] <= nums[index[mid + 1]]) return;int i = l, j = mid + 1, k = l;while (i <= mid && j <= r) {if (nums[index[i]] <= nums[index[j]]) {ret[index[i]] += j - mid - 1;index_temp[k++] = index[i++];}else index_temp[k++] = index[j++];}while (i <= mid) {ret[index[i]] += j - mid - 1;index_temp[k++] = index[i++];}while (j <= r) index_temp[k++] = index[j++];for (i = l; i <= r; i++) index[i] = index_temp[i];}vector<int> countSmaller(vector<int>& nums) {int n = nums.size();index_temp.resize(n);ret.resize(n);vector<int> index(n);for (int i = 0; i < n; i++) {index[i] = i;}mergeSort(nums, index, 0, n - 1);return ret;}
};

💗感谢阅读！💗