Daily Archives: December 13, 2015

Leetcode – Count of Smaller Numbers After Self

Here is leetcode’s new hard level question:
https://leetcode.com/problems/count-of-smaller-numbers-after-self/

The basic idea is using two for to loop though to counter smaller number on its left.
Solution1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

public List<Integer> countSmaller(int[] nums) {
List<Integer> result = new ArrayList<>();
 
result.add(0);
 
for(int i = nums.length - 2;i>=0;i--)
{
    int target = nums[i];
    int count = 0;
    for(int j=i+1;j<=nums.length-1;j++)
    {
        if(nums[j]<=target)
            count++;
    }
    result.add(count);
}
 
Collections.reverse(result);
 
return result;
}

Solution 2:

Solution 1 is using two loops to go though to compare.

This solution is faster the second loop using tree.

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

 
package leetcodetest;
 
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
 
/**
 *
 * @author wudi
 */
public class CountSmaller2 {
 
    public class xTreenode
    {
        public xTreenode left = null;
        public xTreenode right = null;
        int count = 1;
 
        int val;
 
        public xTreenode(int x)
        {
            val = x;
        }
 
    }
 
    public int add(xTreenode root,int x)
    {
        int count = 0;
 
        while(true)
        {
            if(x <= root.val)
            {
                root.count++;
 
                if(root.left == null){
                    root.left = new xTreenode(x);
                    break;
                }
 
                root = root.left;
            }
            else
            {
                count += root.count;
                if(root.right == null)
                {
                    root.right = new xTreenode(x);
                    break;
                }
                root = root.right;
            }
        }
 
        return count;
    }
 
    public List<Integer> countSmaller(int[] nums) {
        List<Integer> result = new ArrayList<>();
        if(nums == null || nums.length == 0) 
            return result;
        xTreenode root = new xTreenode(nums[nums.length - 1]);
        result.add(0);
 
        for(int i=nums.length - 2;i>=0;i--)
        {
            int count = add(root,nums[i]);
            result.add(count);
        }
 
        Collections.reverse(result);
 
        return result;
    }
     public static void main(String[] args) {
         int[] nums = {2,0,1};
 
        CountSmaller2 c = new CountSmaller2();
        System.out.println(c.countSmaller(nums));
     }
}