315. Count of Smaller Numbers After Self

cnio 发布于2019-08-14 17:34 / 2003人阅读

摘要：题目链接的题，用来做，这种求有多少的题一般都是。里多加一个信息表示以为的节点数。也可以做，因为是统计有多少的，其实就是求从最小值到的。的是，要做一个映射，把的值映射到之间。所以先把给一下，用一个来做映射。还有的方法，参考

315. Count of Smaller Numbers After Self

题目链接：https://leetcode.com/problems...

divide and conquer的题，用bst来做，这种求有多少smaller的题一般都是bst。node里多加一个信息：size表示以node为subtree的节点数。

public class Solution {
    public List countSmaller(int[] nums) {
        /* binary search tree 
         */
        int n = nums.length;
        LinkedList res = new LinkedList();
        if(n == 0) return res;
        
        res.add(0);
        Node root = new Node(nums[n-1]);
        for(int i = n - 2; i >= 0; i--) {
            res.addFirst(findSmaller(root, nums[i]));
        }
        return res;
    }
    
    private int findSmaller(Node root, int value) {
        int res = 0;
        while(root != null) {
            root.size += 1;
            if(root.val < value) {
                // add root and all left nodes
                res += 1 + (root.left == null ? 0 : root.left.size);
                if(root.right == null) {
                    root.right = new Node(value);
                    break;
                }
                root = root.right;
            }
            else {
                if(root.left == null) {
                    root.left = new Node(value);
                    break;
                }
                root = root.left;
            }
        }
        return res;
    }
    
    class Node {
        int val;
        Node left;
        Node right;
        // count the size of this subtree
        int size;
        Node(int val) { this.val = val; this.size = 1; }
    }
}

binary index tree也可以做，因为是统计有多少smaller的，其实就是求从最小值到nums[i] - 1的sum。tree的index是nums[i]，要做一个映射，把nums[i]的值映射到[1, # of unique numbers in nums]之间。所以先把array给sort一下，用一个map来做映射。

public class Solution {
    public List countSmaller(int[] nums) {
        /* binary index tree 
         */
        // reflection first, key: nums[i], value: order
        Map map = new HashMap();
        int[] sorted = Arrays.copyOf(nums, nums.length);
        Arrays.sort(sorted);
        // record the order
        int idx = 1;
        for(int i = 0; i < nums.length; i++) {
            if(!map.containsKey(sorted[i])) map.put(sorted[i], idx++);
        }
        // range will be [1, idx]
        BIT t = new BIT(idx);
        LinkedList res = new LinkedList();
        for(int i = nums.length - 1; i >= 0; i--) {
            int sum = t.sum(map.get(nums[i]) - 1);
            res.addFirst(t.sum(map.get(nums[i]) - 1));
            t.add(map.get(nums[i]), 1);
        }
        return res;
    }
    
    class BIT {
        int[] tree;
        int n;
        BIT(int n) { this.n = n; tree = new int[n]; }
        // sum the smaller elements
        protected int sum(int i) {
            int res = 0;
            while(i > 0) {
                res += tree[i];
                i -= (i & -i);
            }
            return res;
        }
        
        protected void add(int i, int val) {
            while(i < n) {
                tree[i] += val;
                i += (i & -i);
            }
        }
    }
}

还有merge sort的方法，参考discussion：
https://discuss.leetcode.com/...

服务器托管混合云 Smaller Numbers 315cdn after()

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/66675.html

leetcode315. Count of Smaller Numbers After Self

摘要：当我们希望查询时，则从根节点开始寻找其所在的区间，如果位于左侧区间，则查询左子树啊，如果位于右侧区间，则查询右子树。如果横跨了分割点，则分别查询左子树的部分和右子树的部分。题目要求 You are given an integer array nums and you have to return a new counts array. The counts array has t...

elarity 2019-08-15 15:09 评论0 收藏0
Leetcode[315] Count of Smaller Numbers After Self

摘要：复杂度思路每遍历到一个数，就把他到已有的中。对于每一个，维护一个和一个自身的数目。比如，然后每次遍历到一个数，就把对应位置的值加一。比如碰到之后，就变成，然后统计的和。 Leetcode[315] Count of Smaller Numbers After Self ou are given an integer array nums and you have to return a...

dack 2019-08-14 16:41 评论0 收藏0
leetcode 315 Count of Smaller Numbers After Self

摘要：我们建立的，其中解决重复值的问题，记录左子树的节点数。给定要找的点，这里的规律就是，往右下走，说明当前点和当前的的左子树的值全部比小。我们走到要向右，这是左子树没变化，这里也不变。题目细节描述参看leetcode。今天的重头戏 LC315 Count of Smaller Numbers After Self.在讲这个题目之前，请思考这个问题。在BST找到所有比Node P小的节点...

Little_XM 2019-08-14 17:20 评论0 收藏0
leetcode 315 Count of Smaller Numbers After Self 以

摘要：题目意思就是要一个个的返回当前的最小值。所以解法自然就是。我们需要找出被打乱的点并返回正确结果。然后将两个不正确的点记录下来，最后回原来正确的值。如果是叶子节点，或者只有一个子树。思想来自于的代码实现。跳过总结请点这里：https://segmentfault.com/a/11... BST最明显的特点就是root.left.val < root.val < root.right.v...

inapt 2019-08-14 17:20 评论0 收藏0
[LeetCode] 315. Count of Smaller Numbers After Sel

Problem You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i]. Exam...

FingerLiu 2019-08-16 13:53 评论0 收藏0