Leetcode[315] Count of Smaller Numbers After Self

dack 发布于2019-08-14 16:41 / 2469人阅读

摘要：复杂度思路每遍历到一个数，就把他到已有的中。对于每一个，维护一个和一个自身的数目。比如，然后每次遍历到一个数，就把对应位置的值加一。比如碰到之后，就变成，然后统计的和。

Leetcode[315] Count of Smaller Numbers After Self

ou 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].

Binary Search Tree

复杂度
O(NlgN), O(N)

思路
每遍历到一个数，就把他insert到已有的BST中。对于每一个node，维护一个leftsum和一个自身的cnt数目。所以对于一个Node来说，比他小的值，应该是每次向右走的时候，就将结果累积到prenum中，其中prenum = node.leftsum + node.cnt

代码

class Node {
    int val;
    int leftSum;
    int cnt;
    Node left;
    Node right;
    public Node(int val) {
        this.val = val;
    }
}


LinkedList res;
public List countSmaller(int[] nums) {
    res = new LinkedList<>();
    Node root = new Node();
    for(int i = nums.length - 1; i >= 0; i --) {
        helper(nums[i], root, 0);
    }
}

public Node helper(int val, Node root, int preNum) {
    if(root == null) {
        res.addFirst(preNum);
        return new Node(val);
    }
    if(root.val == val) {
        root.cnt ++;
        res.addFirst(preNum + root.leftSum);
    }
    else if(root.val > val) {
        root.leftSum ++;
        root.left = helper(val, root.left, preNum);
    }
    else {
        root.right = helper(val, root.right, preNum + root.leftSum + root.cnt);
    }    
    return root;
}

Binary Index Tree

复杂度
O(NlgN), O(N)

思路
建立一个包含从min到max的数组，[5,2,6,1]，然后对于每一个数，考虑从Min到比这个数的小的所有数的和。
比如[1,2,3,4,5,6]=[0,0,0,0,0,0]，然后每次遍历到一个数，就把对应位置的值加一。
比如碰到1之后，就变成[1,0,0,0,0,0]，然后统计sum[val - 1]的和。

代码

int[] BItree;

public List countSmaller(int[] nums) {
    int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
    LinkedList res = new LinkedList<>();
    if(nums == null || nums.length == 0) return res;
    //
    for(int val : nums) {
        min = Math.min(min, val);
    }
    int diff = 1 - min;
    for(int i = 0; i < nums.length; i ++) {
        nums[i] += diff;
        max = Math.max(max, nums[i]);
    }
    //
    BItree = new int[max + 1];
    for(int i = nums.length - 1; i >= 0; i --) {
        res.addFirst(getSum(nums[i] - 1));
        update(nums[i], BItree.length);
    }
    return res;
}

public int getSum(int index) {
    int res = 0;
    while(index > 0) {
        res += BItree[index];
        index -= index & (-index);
    }
    return res;
}

public void update(int index, int len) {
    while(index < len) {
        BItree[index] ++;
        index += index & (-index);
    }
}

专线服务云服务器 Smaller Numbers 315cdn LeetCode

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

转载请注明本文地址：https://www.ucloud.cn/yun/66253.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。今天的重头戏 LC315 Count of Smaller Numbers After Self.在讲这个题目之前，请思考这个问题。在BST找到所有比Node P小的节点...

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

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

cnio 2019-08-14 17:34 评论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