LeetCode 315. 计算右侧小于当前元素的个数

我就是我 2022-10-29 05:25 162阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70]

//解法一：分治 用额外的index数组记录下标 根据index归并排序并计算答案 有点慢我日
    class Solution {
        
        int[] res;
        int[] tmp;
        int[] index;
        public List<Integer> countSmaller(int[] nums) {
        
            int n = nums.length;
            res = new int[n];
            tmp = new int[n];
            index = new int[n];
            for(int i = 0; i < n; i++)
                index[i] = i;
            merge(nums, 0, n - 1);
            List<Integer> list = new ArrayList<Integer>();
            for(int num : res){
        
                list.add(num);
            }
            return list;
        }
    
        public void merge(int[] a, int l, int r){
        
            if(l == r)
                return;
            int mid = l + r >> 1;
            merge(a, l, mid);
            merge(a, mid + 1, r);
            if(a[index[mid]] <= a[index[mid + 1]])
                return;
            
            //合并
            for(int i = l; i <= r; i++)
                tmp[i] = index[i];
            int i = l;
            int j = mid + 1;
            for(int k = l; k <= r; k++){
        
                if(i > mid){
        
                    index[k] = tmp[j++];
                }else if(j > r){
        
                    index[k] = tmp[i++];
                    res[index[k]] += (r - mid);
                }else{
        
                    if(a[tmp[i]] <= a[tmp[j]]){
        
                        index[k] = tmp[i++];
                        res[index[k]] += j - mid - 1;
                    }else{
        
                        index[k] = tmp[j++];
                    }
                }
            }
        }
    }

//解法二：树状数组 慢。。。。
    class Solution {
        
        public List<Integer> countSmaller(int[] nums) {
        
            LinkedList<Integer> res = new LinkedList<>();
            int len = nums.length;
            if(len == 0) return res;
            //将nums中的元素排序，记录每个元素对应的索引
            TreeSet<Integer> set = new TreeSet();
            for(int i = 0; i < len; i++){
        
                set.add(nums[i]);
            }
            Map<Integer, Integer> map = new HashMap<>();
            int index = 1;
            for(Integer n : set){
        
                map.put(n, index);
                index++;
            }
            //利用索引更新并统计
            FenwickTree fenwickTree = new FenwickTree(len + 1);
            for(int i = len - 1; i >= 0; i--){
        
                index = map.get(nums[i]);
                //在索引位置添加计数1
                fenwickTree.update(index, 1);
                //统计比索引对应元素小的个数
                res.addFirst(fenwickTree.query(index - 1));
            }
            return res;
        }
    
        //线段树，O(logn)实现单点更新和前缀和计算
        private class FenwickTree {
        
    
            private int[] tree;
            private int len;
    
            public FenwickTree(int n) {
        
                this.len = n;
                tree = new int[n + 1];
            }
            //更新本节点和父节点
            public void update(int i, int delta) {
        
                while (i <= this.len) {
        
                    tree[i] += delta;
                    i += lowbit(i);
                }
            }
            //求和，找到对应树的节点
            public int query(int i) {
        
                int sum = 0;
                while (i > 0) {
        
                    sum += tree[i];
                    i -= lowbit(i);
                }
                return sum;
            }
            //计算第一个非0的位置，2的幂
            public int lowbit(int x) {
        
                return x & (-x);
            }
        }
    }

//解法三：线段树 也慢。。。
    class Solution {
        
        public List<Integer> countSmaller(int[] nums) {
        
            LinkedList<Integer> res = new LinkedList<>();
            int len = nums.length;
            if(len == 0) return res;
            //获取区间范围
            int start = nums[0], end = nums[0];
            for(int i = 0; i < len; i++){
        
                if(nums[i] < start) start = nums[i];
                if(nums[i] > end) end = nums[i];
            }
            //构建树
            SegmentTreeNode root = build(start, end);
            //从右向左，边插入边计数
            for(int i = len - 1; i >= 0; i--){
        
                //计数小于该元素的区间，所以要减一
                res.addFirst(count(root, start, nums[i] - 1));
                insert(root, nums[i], 1);
            }
            return res;
        }
        //线段树节点，包含左右最值和该区间叶子节点数，子区间不断递减
        private class SegmentTreeNode{
        
            int start, end, count;
            SegmentTreeNode left, right;
    
            public SegmentTreeNode(int start, int end){
        
                this.start = start;
                this.end = end;
                this.count = 0;
                left = null;
                right = null;
            }
        }
        //构建线段树，不断递减区间长度
        private SegmentTreeNode build(int start, int end){
        
            if(start > end) return null;
            SegmentTreeNode root = new SegmentTreeNode(start, end);
            if(start != end){
        
                int mid = start + (end - start) / 2;
                root.left = build(start, mid);
                root.right = build(mid + 1, end);
            }
            return root;
        }
        //插入并更新叶子节点
        private void insert(SegmentTreeNode root, int index, int val){
        
    
            if (root.start == index && root.end == index){
        
                root.count += val;
                return;
            }
    
            int mid = root.start + (root.end - root.start) / 2;
            if (index >= root.start && index <= mid)
                insert(root.left, index, val);
            if (index > mid && index <= root.end)
                insert(root.right, index, val);
            //更新父节点的统计数，便于正好落在区间上的查找
            root.count = root.left.count + root.right.count;
        }
        //根据区间统计
        private int count(SegmentTreeNode root, int start, int end){
        
            //nums[i] - 1, 排除相等的情况
            if(start > end) return 0;
            //递归到叶子节点，获取计数值
            if (start == root.start && end == root.end){
        
                return root.count;
            }
            int mid = root.start + (root.end - root.start) / 2;
            int leftcount = 0, rightcount = 0;
            //统计左半区
            if (start <= mid){
        
                if (mid < end)
                    leftcount = count(root.left, start, mid);
                else
                    leftcount = count(root.left, start, end);
            }
            //统计右半区
            if (mid < end){
        
                if (start <= mid)
                    rightcount = count(root.right, mid + 1, end);
                else
                    rightcount = count(root.right, start, end);
            }
            return (leftcount + rightcount);
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70]: /images/20221024/522015f1aad947f8bfc92fd4a7ccde9d.png