【 每天学习一点算法 2026/05/26】计算右侧小于当前元素的个数

每天学习一点算法 2026/05/26题目计算右侧小于当前元素的个数给你一个整数数组 nums 按要求返回一个新数组 counts 。数组 counts 有该性质 counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。这题思路很简单就是遍历数组 nums 计算后续元素小于自身的个数。重点在于如何优化时间复杂度。假如我们从右侧开始遍历将已经遍历的元素进行降序排序那么我们只需要在元素nums[i]右侧已排序的元素中找到第一个小于nums[i]的元素nums[j]nums[j]及它后面的元素就都是小于nums[i]的而且我们找到的位置j正是我们进行后续排序插入的nums[i]的位置所以我们可以计算count[i]的同时进行排序操作。由于实在排序数组中寻找元素所以我们可以利用二分查找进一步进行优化。functioncountSmaller(nums:number[]):number[]{constlennums.lengthif(len1)return[0]// 长度为 1 直接返回 [0]constcountsnewArray(len).fill(0)// 结果数组constsortList:number[][nums[len-1]]// 已排序部分// 从右往左遍历for(letilen-2;i0;i--){constjfindSmaller(nums[i])// 获取当前元素插入位置if(jsortList.length){// 如果插入位置在末尾表示没有小于它的元素sortList.push(nums[i])counts[i]0}else{// 插入位置后的元素个数就是小于它的元素个数counts[i]sortList.length-j sortList.splice(j,0,nums[i])}}returncounts// 辅助函数二分查找第一个小于目标的元素的位置functionfindSmaller(target:number):number{letleft0,rightsortList.length-1letressortList.lengthwhile(leftright){constmidMath.floor((leftright)/2)if(targetsortList[mid]){resmid rightmid-1}else{leftmid1}}returnres}};我还纳闷这题怎么在树和图的题解里面看了官方题解提到了树状数组emmm 有点复杂。待我研究研究明天写一篇树状数组的文章题目来源力扣LeetCode