高级结构 查找 排序-维护X的秩

现在我们要读入一串数，同时要求在读入每个数的时候算出它的秩，即在当前数组中小于等于它的数的个数(不包括它自身)，请设计一个高效的数据结构和算法来实现这个功能。
给定一个int数组A，同时给定它的大小n，请返回一个int数组，元素为每次加入的数的秩。保证数组大小小于等于5000。
测试样例：
[1,2,3,4,5,6,7],7
返回：[0,1,2,3,4,5,6]

import java.util.*;
public class Rank {
    public int[] getRankOfNumber(int[] A, int n) {
        // write code here
        int R[] = new int[n];
        for(int i = 1;i< n;i++){
            for(int j = 0;j<i;j++){
                if(A[j]<= A[i])
                    R[i]+=1;
            }
        }
        return R;
    }
}

import java.util.*;
/*
用一个二叉查找树来维护当前已经插入的数组，小于等于该节点插入左子树内，
大于插入右子树内，递归调用。
这样，每次查询小于等于某个节点的节点数，分三种情况讨论，递归调用：
1.当前节点的值等于插入的节点的值，那么返回该节点的左子树数目就等于秩
2.当前节点的值大于插入的节点的值，那么递归调用左子树（因为该节点的本身
及其右子树都对秩没影响)
3.当前节点的值小于插入的节点的值，那么当前节点的所有左子树加上本身都是
该插入节点的秩，
然后加上插入的节点在右子树中的秩之和为改插入节点的秩
 
注意：1.只用记录当前节点的左子树的个数，2.每次都是先插再找出秩，所以每
次查找不会出现不在树中的情况。
*/
public class Rank {
    Node root = null;
 
    public int[] getRankOfNumber(int[] A, int n) {
        int res[] = new int[n];
        for (int i = 0; i < n; i++) {
            res[i] = helper(A[i]);
        }
        return res;
    }
 
    public int helper(int a) {
        if (root == null) {
            root = new Node(a);
        } else {
            root.insert(a);
        }
        return root.getRank(a);
    }
}
 
class Node {
    int leftSize = 0; 
    Node left, right;
    int val;
 
    public Node(int v) {
        val = v;
    }
 
    public void insert(int v) {
        if (v <= val) {
            if (left != null)
                left.insert(v);
            else
                left = new Node(v);
            leftSize++;
        } else {
            if (right != null)
                right.insert(v);
            else
                right = new Node(v);
        }
    }
 
    public int getRank(int v) {
        if (v == val)
            return leftSize;
        if (v < val)
            return left.getRank(v);
        if (v > val)
            return leftSize + 1 + right.getRank(v);
        return 0;
    }
}

http://m.blog.csdn.net/eversliver/article/details/52398226