优化使用二分查找的Climbing Leaderboard代码执行时长

需求：基于排行榜（ranked）数组与玩家分数（player）数组生成玩家排名数组。现有代码功能正常，但处理包含20万条元素的大规模ranked数组时会超时，寻求优化方案，无需提供可直接复制的代码。

现有代码 #

int* climbingLeaderboard(int ranked_count, int* ranked, int player_count, int* player, int* result_count) {
    
    *result_count=player_count;
    // remove duplicates
    int removed=0;
    for(int i=0, j=1; i<ranked_count-removed; i++, j++){   
      if(ranked[i]==ranked[j]){
        for(int k=j; k<ranked_count-removed; k++) 
           ranked[k]=ranked[k+1]; 
        removed++;
      }
    }
    int newsize=ranked_count-removed;
    // create an array to store ranks then fill it
    int* positions=malloc(newsize*sizeof(int));
    positions[0]=1;
    for(int i=0, j=1; j<newsize; i++, j++){
        positions[j]=(ranked[j]<ranked[i])? (positions[i]+1) : positions[i];
    }
    // create and fill the results array using binary search
    int* res = malloc(player_count*sizeof(int));
    int start=0, end=newsize-1, middle=(start+end)/2;
    int j, k=newsize-1;
    for(int i=0; i<player_count; i++){
        if(i>0&&player[i]==player[i-1]){
            *(res+i)=(*(res+(i-1))); 
            continue;
        }
        if(player[i]>=ranked[middle]){
            *(res+i)=positions[middle]; 
            j=middle-1;
            while(j>=0){
                if(player[i]>=ranked[j]) 
                    *(res+i)=positions[j];
                else if(j==k) 
                    *(res+i)=positions[j]+1; 
                else break; 
                --j;
            }
            start=0; end=middle-1;
        }
        else{
            *(res+i)=positions[newsize-1]+1; 
            j=newsize-1;
            while(j>=middle){
                if(player[i]>=ranked[j]) 
                    *(res+i)=positions[j];
                else if(j==k) 
                    *(res+i)=positions[j]+1; 
                else break; 
                --j;
            }
            start=middle+1; end=newsize-1;
        }
        middle=(start+end)/2;
    }
    free(positions);
    return res;
}

优化方向 #

• 去重逻辑优化：原去重采用嵌套循环+元素平移的方式，时间复杂度为O(n²)，大规模数据下开销极大。改为一次遍历构建去重后的新数组，仅需O(n)时间，避免频繁移动数组元素的操作。
• 排名计算合并：将排名数组（positions）的生成与去重步骤合并，在构建去重数组的同时直接计算每个位置的排名，减少一次单独遍历的开销。
• 二分查找逻辑修复：原代码的二分查找后附加了线性扫描，没有发挥二分查找O(logn)的优势。实现完整的二分查找，精准定位玩家分数在去重排行榜中的位置，直接映射到对应排名，无需后续线性遍历。此外，若玩家分数数组是递增有序的，可以利用该特性，保持二分查找的指针不重置，或从排行榜末尾反向遍历，进一步降低查找次数。
• 内存精简：若允许修改原ranked数组，可直接在原数组上完成去重操作，避免额外的内存分配；或者取消单独的positions数组，直接在去重后的排行榜数组中存储对应排名，减少内存占用与访问开销。

内容的提问来源于stack exchange，提问作者redone_l