Count of Smaller Number before itself 249

Question

Give you an integer array (index from 0 to n-1, where n is the size of this array, value from 0 to 10000) . For each element Ai in the array, count the number of element before this element Ai is smaller than it and return count number array.

Example

For array [1,2,7,8,5], return [0,1,2,3,2]

Solution

SegmentTree里唯一一道还有点难度的题。

1. 首先以0-10000为区间建树，并将所有区间count设为0。每一个最小区间（即叶节点）的count代表到目前为止遇到的该数的数量。

2. 然后开始遍历数组，遇到A[i]时，去查0-A[i]-1区间的count，即为比A[i]小的数的数量

3. 查完后将A[i]区间的count加1即可

代码如下：

public class Solution {
   /**
     * @param A: An integer array
     * @return: Count the number of element before this element 'ai' is 
     *          smaller than it and return count number array
     */ 
    class SegmentTreeNode {
        public int start, end;
        public int count;
        public SegmentTreeNode left, right;
        public SegmentTreeNode(int start, int end, int count) {
              this.start = start;
              this.end = end;
              this.count = count;
              this.left = this.right = null;
        }
    }

    SegmentTreeNode root;

    private SegmentTreeNode build(int start, int end){
        if(start > end){
            return null;
        }

        SegmentTreeNode root = new SegmentTreeNode(start, end, 0);

        if(start != end){
            int mid = (start + end) / 2;
            root.left = build(start, mid);
            root.right = build(mid + 1, end);
        }

        return root;
    }

    private int query(SegmentTreeNode root, int start, int end){
        if(start == root.start && end == root.end){
            return root.count;
        }

        int leftCount = 0;
        int rightCount = 0;

        int mid = (root.start + root.end) / 2;
        if(start <= mid){
            if(end > mid){
                leftCount = query(root.left, start, mid);
            }else{
                leftCount = query(root.left, start, end);
            }
        }

        if(end > mid){
            if(start <= mid){
                rightCount = query(root.right, mid + 1, end);
            }else{
                rightCount = query(root.right, start, end);
            }
        }

        return leftCount + rightCount;
    }

    private void modify(SegmentTreeNode root, int index, int value){
        if(root.start == index && root.end == index){
            root.count += value;
            return;
        }

        int mid = (root.start + root.end) / 2;
        if(index >= root.start && index <= mid){
            modify(root.left, index, value);
        }

        if(index <= root.end && index > mid){
            modify(root.right, index, value);
        }

        root.count = root.left.count + root.right.count;
    }

    public ArrayList<Integer> countOfSmallerNumberII(int[] A) {
        // write your code here
        ArrayList<Integer> result = new ArrayList<Integer>();
        if(A == null || A.length == 0){
            return result;
        }

        root = build(0, 10000);
        int ans;
        for(int i = 0; i < A.length; i++){
            ans = 0;
            if(A[i] > 0){
                ans = query(root, 0, A[i] - 1);
            }
            modify(root, A[i], 1);
            result.add(ans);
        }

        return result;
    }
}