leetcode315. Count of Smaller Numbers After Self

elarity 发布于2019-08-15 15:09 / 2974人阅读

摘要：当我们希望查询时，则从根节点开始寻找其所在的区间，如果位于左侧区间，则查询左子树啊，如果位于右侧区间，则查询右子树。如果横跨了分割点，则分别查询左子树的部分和右子树的部分。

题目要求

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

Example:

Given nums = [5, 2, 6, 1]

To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.
Return the array [2, 1, 1, 0].

输入一个整数数组nums[i]，返回所有一个新的数组count，该数组第i位上的count[i]表示nums[i]右侧小于nums[i]的数字的个数。

简单说一说Segment Tree

SegmentTree常常用于对于一个数组有多次范围型查询的场景。比如计算从L到R之间所有元素的和，或者找到L到R之间的最小元素。这里L和R是会移动的。

SegmentTree本质上是一棵二叉树，该二叉树会存储一个区间的某种值，如最大值，最小值或是该区间所有元素的和。如果根节点代表这个数组A[1...N]，那么它的每一个叶节点代表一个元素A[i]，每一个非叶节点代表一个区间A[i...j]，其中0<=i

当我们希望插入一个SegmentTreeNode时，我们要找到更新所在的区间，并且递归的将其下所有的区间作出相应的更改。

当我们希望查询时，则从根节点开始寻找其所在的区间，如果位于左侧区间，则查询左子树啊，如果位于右侧区间，则查询右子树。如果横跨了分割点，则分别查询左子树的部分和右子树的部分。

思路和代码

这里我们将从右往左构建一棵二叉搜索树，这棵树的每个节点还将存储额外的信息，即遍历到nums[i]时，该节点的值重复的数量duplicateCount，以及从i到该节点共有几个数字小于该节点而大于其父节点的值smallerThan（相当于左子树元素的个数）。

直接从例子入手吧：
假设现在有这样一个数组[11,6,9,9,3,1,7]
则构造树的步骤如下：
注：括号中的值分别对用这smallerThan和duplicateCount

插入7
7(0, 1)

此时右侧小于7的数字为0个

插入1
   7(1,1)
  /
1(0,1)

当向左插入节点时，父节点的smallerThan加一。此时我们看到右侧小于1的数字还是0个

插入3
   7(2,1)
  /
1(0,1)
  
   3(0,1)

此时我们看到，3比1大，因此在1处将其作为右节点插入。此时比3小的数字也就是1和所有比1小的数字，即0+1 = 1这里0对应比1小的数字，1对应数字1的重复次数。

   7(2,1)
  /     
1(0,1)   9(0, 1)
  
   3(0,1)

此时我们在根节点7处向右插入节点9，每一次向右插入都意味着有数字比当前的值小，因此比9小的数字的个数为2 + 1 + 0 = 3这里0代表着比7大但是比9小的元素的个数。

插入9
   7(2,1)
  /     
1(0,1)   9(0, 2)
  
   3(0,1)

重复插入9，因此将9的duplicateCount加一，比其小的元素的个数还是为2+1+0=3。

插入6
   7(3,1)
  /     
1(0,1)   9(0, 2)
  
   3(0,1) 
     
      6(0,1)

首先看到根节点7的smallerThan加一，然后将所有右拐处的节点值相加，即0+1 + 0+1 + 0 = 2

插入11
   7(3,1)
  /     
1(0,1)   9(0, 2)
          
   3(0,1)   11(0,1)
     
      6(0,1)

那么小于11的数字有几个呢？没错，就是3+1+0+2+0 = 6

代码实现如下：

    public List countSmaller(int[] nums) {
        LinkedList result = new LinkedList();
        if(nums.length == 0) return result;
        SpecialTreeNode root = new SpecialTreeNode(nums[nums.length-1]);
        result.addFirst(0);
        for(int i = nums.length-2 ; i>=0 ; i--){
            int count = insert(root, nums[i]);
            result.addFirst(count);
        }
        return result;
    }
    
    private int insert(SpecialTreeNode root, int val){
        if(val == root.val){
            root.addDuplicate();
            return root.smallerThan;
        }else if(val < root.val){
            root.addSmallerThan();
            if(root.left==null){
                SpecialTreeNode s = new SpecialTreeNode(val);
                root.left = s;
                return 0;
            }else{
                return insert(root.left, val);
            }
        }else{
            if(root.right == null){
                SpecialTreeNode s = new SpecialTreeNode(val);
                root.right = s;
                return root.smallerThan + root.duplicateCount;
            }else{
                return root.smallerThan + root.duplicateCount + insert(root.right, val);
            }
        }
        
    }
    class SpecialTreeNode{
        int val = 0, smallerThan = 0, duplicateCount = 1;
        SpecialTreeNode left;
        SpecialTreeNode right;
        
        SpecialTreeNode(int val){
            this.val = val;
        }
        
        void addDuplicate(){
            this.duplicateCount++;
        }
        
        void addSmallerThan(){
            this.smallerThan++;
        }
    }

参考文章

Segment Tree Tutorials

想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~

GPU云服务器云服务器 Smaller Numbers 315cdn Leetcod

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

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

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
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