HackerRank Sorting 4.Fraudulent Activity Notifications

我只想到用 Counting Sort (O(n*exp[i]_range))。

int activityNotifications(vector<int> e, int d) {
    int ct=0;
    vector<int> m(205,0);
    for(int i=0;i<d;i++){
        m[e[i]]++;
    }
    for(int i=d;i<e.size();i++){
        int k=0,p=-1;
        for(int j=0;j<201;j++){
            k+=m[j];
            if(d&1){
                if(k>=d/2+1){
                    if(e[i]>=j*2) ct++;
                    break;
                }
            }else{
                if(k==d/2){
                    p=j;
                }else if(k>d/2){
                    if(p==-1){
                        if(e[i]>=j*2) ct++;
                    }else{
                        if(e[i]>=j+p) ct++;
                    }
                    break;
                }
            }
        }
        m[e[i]]++;
        m[e[i-d]]--;
    }
    return ct;
}

出處:HackerRank

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *