Give you an integer array (index from 0 to n-1, where n is the size of this array, value from 0 to 10000) and an query list. For each query, give you an integer, return the number of element in the array that are smaller than the given integer.

Notice

We suggest you finish problemSegment Tree BuildandSegment Tree Query IIfirst.

Have you met this question in a real interview?

Yes

Example

For array[1,2,7,8,5], and queries[1,8,5], return[0,4,2]

思路是

如果数组的元素个数多于10000， 则建一棵0-10000的树，可以然后逐个把元素添加进树，或者用一个hash先存起来(额外空间）但省了k(logn)的时间复杂度，因为在建树过程中便可以一步到位

建树的目标是建一个0，最大值 的线段树，记录每一个线段的元素个数，那么在query时，就可以query 0 到 查询数 - 1区间的元素个数从而做到logn 查询

class SegmentTree {
    int start, end, count, max, min;
    SegmentTree left, right;
    public SegmentTree(int start, int end, int count, int max, int min) {
        this.start = start;
        this.end = end;
        this.count = count;
        this.max = max;
        this.min = min;
    }
}

public class Solution {
    /*
     * @param A: An integer array
     * @param queries: The query list
     * @return: The number of element in the array that are smaller that the given integer
     */

    public SegmentTree build(int[] A) {
        if (A == null || A.length == 0) {
            return null;
        }
        int max = Integer.MIN_VALUE;
        HashMap<Integer, Integer> hash = new HashMap<Integer, Integer>();
        for (int i = 0; i < A.length; i++) {
            max = Math.max(max, A[i]);
            if (hash.containsKey(A[i])) {
                hash.put(A[i], hash.get(A[i]) + 1);
            } else {
                hash.put(A[i], 1);
            }
        }

        return helper(0, max + 1, hash);


    }

    public SegmentTree helper(int start, int end, HashMap<Integer, Integer> hash) {

        if (start == end) {
            if (hash.containsKey(start)) {
                return new SegmentTree(start, start, hash.get(start), start, start);
            } else {
                return new SegmentTree(start, start, 0, 0, 0);
            }
        }

        SegmentTree root = new SegmentTree(start, end, 0, 0, 0);
        int mid = (start + end) / 2;

        SegmentTree left = helper(start, mid, hash);
        SegmentTree right = helper(mid + 1, end, hash);

        root.max = Math.max(left.max, right.max);
        root.min = Math.min(left.min, right.min);
        root.count = left.count + right.count;
        root.left = left;
        root.right = right;

        return root;
    }

    public int query(SegmentTree root, int start, int end) {
        if (root == null) {
            return 0;
        }

        if (root.start >= start && root.end <= end) {
            return root.count;
        }

        int mid = (root.start + root.end) / 2;

        if (end <= mid) {
            return query(root.left, start, end);
        } else if (start > mid) {
            return query(root.right, start, end);
        }

        return query(root.left, start, mid) + query(root.right, mid + 1, end);
    }

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


        SegmentTree root = build(A);
        for (Integer integer : queries) {
            ans.add(query(root, 0, integer - 1));
        }
        return ans;
    }
}