leetcode315.Count of Smaller Numbers After Self

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
7
8
9
10
11
12
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<j<N

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

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

思路和代码

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

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

1
2
插入7
7(0, 1)

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

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

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

1
2
3
4
5
6
插入3
   7(2,1)
  /
1(0,1)
  \
   3(0,1)

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

1
2
3
4
5
   7(2,1)
  /     \
1(0,1)   9(0, 1)
  \
   3(0,1)

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

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

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

1
2
3
4
5
6
7
8
插入6
   7(3,1)
  /     \
1(0,1)   9(0, 2)
  \
   3(0,1) 
     \
      6(0,1)

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

1
2
3
4
5
6
7
8
插入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

代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
public List<Integer> countSmaller(int[] nums) {
    LinkedList<Integer> result = new LinkedList<Integer>();
    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