Stream Integer

出处

Having a stream of integers, design a data structure to support easy look up the number of values less than or equal to a given value.

Solution

需要一个动态的数据结构，支持快速检索，并且满足一定的有序性，这样才能维护这个特殊属性(给定值在这个有序结构中的相对位置)，使用二叉搜索树。(注意堆没有其他数据结构例如哈希表的辅助，无法支持给定key的快速检索。)

Complexity

与 BST 复杂度一致

Code

class Node{
    private:
        Node* trackhelp(Node*rt,int x);
    public:
        Node *left;
        Node *right;
        int key;
        int left_cnt;
        void track(int x);
        int getRank(int x);
        Node(int key,Node*l = NULL,Node*r =NULL,int cnt = 0):key(key),left(l),right(r),left_cnt(cnt){};
};

Node *Node::trackhelp(Node*rt, int x){
    if( rt == NULL) return new Node(x);
    if( x <= rt->key ){
        rt->left = trackhelp(rt->left,x);
        rt->left_cnt++;
    } else {
        rt->right = trackhelp(rt->right,x);
    }
    return rt;
}

void Node::track( int x){
     trackhelp(this,x);
}

int Node::getRank(int x){
    if(this == NULL) return -1;
    if(x == key)
       return left_cnt;
    if(x < key)
      return left->getRank(x);
    if(x > key){
        if(right->getRank(x) == -1) return -1;
        return left_cnt + 1 + right->getRank(x);
    }
}