网站建设设备预算,wordpress充值金币的插件,电商网站里的水果图片怎么做的,网站的域名和密码是什么意思leetcode315. 计算右侧小于当前元素的个数(树状数组解法) 题目#xff1a;给定一个整数数组 nums#xff0c;按要求返回一个新数组 counts。数组 counts 有该性质#xff1a; counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。
树状数组解法 java
class Solution …leetcode315. 计算右侧小于当前元素的个数(树状数组解法) 题目给定一个整数数组 nums按要求返回一个新数组 counts。数组 counts 有该性质 counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。
树状数组解法 java
class Solution {public ListInteger countSmaller(int[] nums) {ArrayListInteger resnew ArrayList();int nnums.length;if(n0) return res;//利用二叉搜索树SetInteger setnew TreeSet();for(int c:nums) set.add(c);//生成排名表int level1;HashMapInteger,Integer mapnew HashMap();for(int c:set){map.put(c,level);level;}fenWickTree helpernew fenWickTree(set.size()1);for(int in-1;i0;i--){int tempmap.get(nums[i]);//当前元素的排名helper.update(temp,1);//将当前元素的名次更新数字数组res.add(helper.query(temp-1));//查询小于当前元素的}Collections.reverse(res);return res;}class fenWickTree//树状数组{int[] sum;int len;public fenWickTree(int n){lenn;sumnew int[n1];}public int lowBits(int x){return x(-x);}public void update(int i,int num){while (ilen){sum[i]num;ilowBits(i);}}public int query(int i){int res0;while (i0){ressum[i];i-lowBits(i);}return res;}}
}
