Interview question 10.10 Rank of digital stream

Interview questions 10.10. Rank of digital stream

Suppose you are reading a string of integers . Every once in a while , You want to find out the numbers x The rank of ( Less than or equal to x The number of values of ). Please implement data structures and algorithms to support these operations , in other words ：

Realization track(int x) Method , This method is called every time a number is read in ;

Realization getRankOfNumber(int x) Method , Returns less than or equal to x The number of values of .

Be careful ： This question is slightly changed from the original one

Example :

Input :
[“StreamRank”, “getRankOfNumber”, “track”, “getRankOfNumber”]
[[], [1], [0], [0]]
Output :
[null,0,null,1]

This question is very simple , Those who are interested can practice

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); */