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]
Challenge
Could you use three ways to do it.
- Just loop
- Sort and binary search
- 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++) {
result.add(0);
}
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) {
result.add(end + 1);
} else if (A[start] < target) {
result.add(start + 1);
} else {
result.add(0);
}
}
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 elementAi 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的方法了因为顺序不能改变。
建一个0-10000的值型线段树。然后每个叶子节点代表这个值的count。所以在A[i]之前比它小的数的个数就是那个0~A[i]-1这个node 的count值。之后每次Query以后把A[i]那个leaf node count++, 相应回溯更新它所有父亲节点。
时间复杂度是O(m + nlogm) m是值的区间，n是query个数。
这个算法是否最优需要分情况，如果值特别分散且query数特别小，那还不如每次query用O(n)的时间count它之前的比她小的数。
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) {
result.add(0);
} else {
result.add(query(node, 0, A[i] - 1));
}
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;
}
}
