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里唯一一道还有点难度的题。
首先以0-10000为区间建树,并将所有区间count设为0。每一个最小区间(即叶节点)的count代表到目前为止遇到的该数的数量。
然后开始遍历数组,遇到A[i]时,去查0-A[i]-1区间的count,即为比A[i]小的数的数量
查完后将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;
}
}