315. Count of Smaller Numbers After Self

题目大意是给定一个数组，要求输出一个数组，输出的数组要求是：统计原数组每个数值右边比它小的个数，然后记录到输出的数组中。

Input: [5,2,6,1]
Output: [2,1,1,0]
Explanation:
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.

首先尝试了暴力解法，这是最容易想到的解法了，竟然能过，可见测试的数组长度还不是很大。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public List<Integer> countSmaller(int[] nums) {
        int n = nums.length;
        List<Integer> res = new ArrayList<>();
        for(int i=0; i<n; i++) {
            int k = 0;
            for(int j = i+1; j<n; j++) {
                if(nums[j] < nums[i]) {
                    k++;
                }
            }
            res.add(k);
        }
        return res;        
    }
}

O(n²)的解法显然不是最好的，于是看了一下Discuss，选了下面这个符合BST系列的解法。首先一定要倒序遍历原数组开始构造BST，这样构造树的时候能记录所有比它小的节点的个数。至于如何记录的，就是维护两个数值，一个值是当前节点的个数（selfCount），当节点重复时，这个值便递增+1，默认是1。另一个值是所有比当前节点小的节点的个数（leftCount）。这样每次新来一个节点，当需要往右分支插入的时候，那说明比当前节点大，于是新的节点需要加上当前节点的leftCount和selfCount，而往左分支插入的时候是比当前节点小，那么当前节点需要增加一下自身的leftCount。

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
class Solution {
    class Node {
        Node left;
        Node right;
        int val;
        int selfCount = 1;  //自身重复节点个数
        int leftCount;      //所有比自己小的节点个数
        public Node(int val, int left) {
            this.leftCount = left;
            this.val = val;
        }
    }
    
    public List<Integer> countSmaller(int[] nums) {
        Integer[] res = new Integer[nums.length];
        Node node = null;  //返回的永远是根节点
        for(int i=nums.length - 1; i>=0; i--) {
            node = insert(nums[i], res, i, node, 0);
        }
        return Arrays.asList(res);
    }
    public Node insert(int val, Integer[] res, int i, Node t, int leftCount) {
        if(t == null) {
             t = new Node(val, 0);
            res[i] = leftCount;
        } else if(t.val == val) {
            t.selfCount++; 
            res[i] = t.leftCount + leftCount;
        } else if(t.val > val) {
            t.leftCount++;
            t.left = insert(val, res, i, t.left, leftCount);
        } else {
            t.right = insert(val, res, i, t.right, t.leftCount + t.selfCount + leftCount);  
            					//t.leftCount 当前节点所有比它小的节点个数
            					//t.selfCount 自身节点个数， 
            					//leftCount在t节点之前所有满足条件的节点个数
        }
        return t;
    }
    
}

通过这道题主要是练习了一下构造BST的方法，通过记录节点状态来很好的避免之前暴力解法时重复性的比较工作，所以还是要牢记并利用好BST的性质。当然这道题还有个很巧妙的利用Fenwick Tree（Binary Indexed Tree）的解法，思路令人惊叹，我看的是花花酱的讲解。
https://zxi.mytechroad.com/blog/algorithms/array/leetcode-315-count-of-smaller-numbers-after-self/。