面试题 10.10. 数字流的秩

面试题 10.10. 数字流的秩

假设你正在读取一串整数。每隔一段时间，你希望能找出数字 x 的秩(小于或等于 x 的值的个数)。请实现数据结构和算法来支持这些操作，也就是说：

实现 track(int x) 方法，每读入一个数字都会调用该方法；

实现 getRankOfNumber(int x) 方法，返回小于或等于 x 的值的个数。

注意：本题相对原题稍作改动

示例:

输入:
[“StreamRank”, “getRankOfNumber”, “track”, “getRankOfNumber”]
[[], [1], [0], [0]]
输出:
[null,0,null,1]

这题是灰常的简单哈，感兴趣的可以拿到练手

typedef struct {
    
    int val;
    struct StreamRank *next;

} StreamRank;


StreamRank* streamRankCreate() {
    
    StreamRank* s=(StreamRank*)malloc(sizeof(StreamRank));
    s->next=NULL;
    return s;

}

void streamRankTrack(StreamRank* obj, int x) {
    
    StreamRank* s=(StreamRank*)malloc(sizeof(StreamRank));
    s->val=x;
    s->next=obj->next;
    obj->next=s;

    

}

int streamRankGetRankOfNumber(StreamRank* obj, int x) {
    
     StreamRank* s=obj->next;
     int rank=0;
     while(s){
    
         if(s->val<=x){
    
             rank++;
         }
         s=s->next;
     }
     return rank;

}

void streamRankFree(StreamRank* obj) {
    
    free(obj);

}

/** * Your StreamRank struct will be instantiated and called as such: * StreamRank* obj = streamRankCreate(); * streamRankTrack(obj, x); * int param_2 = streamRankGetRankOfNumber(obj, x); * streamRankFree(obj); */