网络异常，图片无法展示
|
给你一个整数数组 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
解题思路
本题首先可以想到的最简单直接的解题方式是双层循环，内层循环遍历外层循环当前元素后面的元素，如果小于当前元素，则当前元素结果值 +1。这样内层循环结束，就得到了外层循环当前元素的右侧小于它的元素的个数。
但是这样的解题方式时间复杂度是 O(n²) 的，无法达到本题的要求。
那如何才能更高效的求得每一个元素右侧小于它的元素的数量呢？
这里我们可以利用归并排序来解题。
在归并排序回溯合并之前，我们假设右区间元素都小于左区间元素，将左区间元素对应结果值都加上右区间元素数量。
在合并过程中，将左区间元素插入结果数组中时，如果此时右区间有未处理的元素，那它们肯定是大于当前左区间元素的，此时需要将当前左区间元素对应的结果值减去右区间未处理元素的数量。
这样，我们就得到了当前合并过程中右区间中小于左区间的元素的数量。 当归并排序完成后，就得到了每一个元素右侧小于它的元素的数量。
动画演示
网络异常，图片无法展示
|
代码实现
var countSmaller = function(nums) { // 获取原数组长度 const len = nums.length, // 初始化temp数组座位归并排序的额外存储空间 temp = Array(len), // 创建下标数组 inds = Array(len), // 初始化结果数组 res = Array(len).fill(0); // 初始化下标数组 for(let i = 0;i<len;i++){ inds[i] = i; } // 因为我们要修改当前值在结果数组对应下标位置的值 // 所以，如果针对数值进行排序的话，排序后是无法得到该数值之前的下标的 // 所以我们需要对下标数组进行排序 // 归并排序 function mergeSort(l,r){ if(l>=r) return; const mid = (l+r)>>1; mergeSort(l,mid) mergeSort(mid+1,r) // 合并之前，假设右区间元素都小于左区间元素，给左区间元素的结果值累加右区间元素数量 for(let i = l;i<=mid;i++){ res[inds[i]] += r-mid } // 回溯合并过程 let k = l,i = l,j = mid+1 while(i<=mid || j<=r){ if(j>r || (i<=mid && nums[inds[i]]<=nums[inds[j]])){ // 插入左区间元素后，右区间剩余的元素一定大于它，所以要给它的结果值减去右区间剩余元素 res[inds[i]] -= r-j+1 temp[k++] = inds[i++] }else{ temp[k++] = inds[j++] } } for(let i = l;i<=r;i++){ inds[i] = temp[i] } } // 调用归并排序方法 mergeSort(0,len-1) // 返回结果数组 return res; }; 复制代码
至此我们就完成了 leetcode-315-计算右侧小于当前元素的个数
如有任何问题或建议，欢迎留言讨论！
