Lintcode 249. Count of Smaller Number before itself

Give you an integer array (index from 0 to n-1, where n is the size of this array, data 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

Example 1:

Input:
[1,2,7,8,5]
Output:
[0,1,2,3,2]

Example 2:

Input:
[7,8,2,1,3]
Output:
[0,1,0,0,2]

Clarification

Before you do this, you'd better complete the following three questions： Segment Tree Build， Segment Tree Query II，and Count of Smaller Number before itself I 。

Notice

We suggest you finish problem Segment Tree Build, Segment Tree Query II and Count of Smaller Number first.

Code (Java):

?

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 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108

public class Solution {     /**      * @param A: an integer array      * @return: A list of integers includes the index of the first number and the index of the last number      */     public List<Integer> countOfSmallerNumberII(int[] A) {         // write your code here         List<Integer> ans = new ArrayList<>();         if (A == null || A.length == 0) {             return ans;         }           SegmentTree segmentTree = new SegmentTree();         segmentTree.build(0, 10000);           for (int num : A) {             int count = segmentTree.query(0, num - 1);             ans.add(count);             segmentTree.modify(num, 1);         }         return ans;     } }   class SegmentTree {     SegmentTreeNode root = null;       public void build(int start, int end) {         root = buildHelper(start, end);     }       public int query(int start, int end) {         return queryHelper(root, start, end);     }       public void modify(int index, int value) {         modifyHelper(root, index, value);     }       private void modifyHelper(SegmentTreeNode root, int index, int value) {         if (root == null) {             return;         }           if (root.start == root.end && root.start == index) {             root.count += value;             return;         }           int mid = root.start + (root.end - root.start) / 2;         if (index <= mid) {             modifyHelper(root.left, index, value);         } else {             modifyHelper(root.right, index, value);         }           root.count = root.left.count + root.right.count;     }       private int queryHelper(SegmentTreeNode root, int start, int end) {         if (root == null || start > end) {             return 0;         }           if (start == root.start && end == root.end) {             return root.count;         }           int mid = root.start + (root.end - root.start) / 2;         int leftCount = queryHelper(root.left, Math.max(start, root.start), Math.min(mid, end));         int rightCount = queryHelper(root.right, Math.max(mid + 1, start), Math.min(root.end, end));           return leftCount + rightCount;     }       private SegmentTreeNode buildHelper(int start, int end) {         if (start > end) {             return null;         }                   if (start == end) {             return new SegmentTreeNode(start, start, 0);         }           int mid = start + (end - start) / 2;         SegmentTreeNode leftChild = buildHelper(start, mid);         SegmentTreeNode rightChild = buildHelper(mid + 1, end);           SegmentTreeNode root = new SegmentTreeNode(start, end, leftChild.count + rightChild.count);         root.left = leftChild;         root.right = rightChild;           return root;     }   }   class SegmentTreeNode {     int start, end;     SegmentTreeNode left, right;     int count;       public SegmentTreeNode(int start, int end, int count) {         this.start = start;         this.end = end;         this.count = count;     } }