# Count of Smaller Number I && II

Count of Smaller Number I

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 that the given integer.

Example

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

Note

We suggest you finish problem Segment Tree Build and Segment Tree Query II first.

Challenge

Could you use three ways to do it.

1. Just loop
2. Sort and binary search
3. Build Segment Tree and Search.

Solution:  Version 1. sort + binary search O(nlogn) Time
//Version 2. Segment Tree. not as efficient as version 1.
//check <Count of Smaller Number II>

```public ArrayList<Integer> countOfSmallerNumber(int[] A, int[] queries) {
//Version 1. sort + binary search
//Version 2. Segment Tree. not as efficient as version 1.
//check <Count of Smaller Number before itself>
ArrayList<Integer> result = new ArrayList<>();
if (A == null || queries == null) {
return result;
}
if (A.length == 0) {
for (int i = 0; i < queries.length; i++) {
}
return result;
}
Arrays.sort(A);
for (int i = 0; i < queries.length; i++) {
int target = queries[i];
//find the last element A[i]<target, i+1 is the number
int start = 0;
int end = A.length - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (A[mid] < target) {
start = mid;
} else {
end = mid;
}
}
if (A[end] < target) {
} else if (A[start] < target) {
} else {
}
}
return result;
}```

Count of Smaller Number II

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]`

Note

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

Solution: Segment Tree. 这道题不能用sort+binary search的方法了因为顺序不能改变。

```public class SegmentTreeNode {
int start, end;
int count;
SegmentTreeNode left;
SegmentTreeNode right;
public SegmentTreeNode(int start, int end) {
this.start = start;
this.end = end;
this.count = 0;
}
}

public ArrayList<Integer> countOfSmallerNumberII(int[] A) {
ArrayList<Integer> result = new ArrayList<>();
if (A == null || A.length == 0) {
return result;
}
SegmentTreeNode node = buildSegmentTree(0, 10000);
for (int i = 0; i < A.length; i++) {
if (A[i] == 0) {
} else {
}
update(node, A[i]);
}
return result;
}

public SegmentTreeNode buildSegmentTree(int start, int end) {
SegmentTreeNode node = new SegmentTreeNode(start, end);
if (start < end) {
int mid = start + (end - start) / 2;
node.left = buildSegmentTree(start, mid);
node.right = buildSegmentTree(mid + 1, end);
node.count = node.left.count + node.right.count;
}
return node;
}

public int query(SegmentTreeNode node, int start, int end) {
if (node.start == start && node.end == end) {
return node.count;
}
int leftCount = 0, rightCount = 0;
int mid = node.start + (node.end - node.start) / 2;
if (start <= mid) {
if (end <= mid) {
leftCount = query(node.left, start, end);
} else {
leftCount = query(node.left, start, mid);
}
}
if (end > mid) {
if (start > mid) {
rightCount = query(node.right, start, end);
} else {
rightCount = query(node.right, mid + 1, end);
}
}
return leftCount + rightCount;
}

public void update(SegmentTreeNode node, int index) {
if (node.start == index && node.end == index) {
node.count = node.count + 1;
} else {
int mid = node.start + (node.end - node.start) / 2;
if (node.start <= index && index <= mid) {
update(node.left, index);
} else if (mid < index && index <= node.end) {
update(node.right, index);
}
node.count = node.left.count + node.right.count; //or node.count = node.count+1;
}
}```
Share