HackerRank Sorting 5.Counting Inversions

這就是反序數對了(Merge Sort)

vector<long> dt;

long msort(long l,long r){
    if(l>=r-1) return 0;
    long mid=(l+r)/2,j=mid;
    long sum=msort(l,mid)+msort(mid,r);
    long tmp[r-l],k=0;
    for(long i=l;i<mid;i++){
        while(j<r && dt[j]<dt[i]){
            tmp[k++]=dt[j++];
        }
        tmp[k++]=dt[i];
        sum+=j-mid;
    }
    while(j<r){
        tmp[k++]=dt[j++];
    }
    j=0;
    for(long i=l;i<r;i++){
        dt[i]=tmp[j];
        j++;
    }
    return sum;
}

出處:HackerRank

發佈留言

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