使用BinarySearch实现Climbing the Leaderboard失败8/12测试用例求助

问题背景 #

在Hackerrank完成实现类挑战时，遇到《Climbing the Leaderboard》问题：给定两个有序整数列表，一个是存在重复元素的降序当前排行榜，另一个是无重复元素的玩家新得分列表。

原解决方案思路：

• 对当前排行榜去重，生成无重复元素的降序列表
• 遍历玩家每个得分，用二分查找在去重后的排行榜中确定排名
• 预估时间复杂度为O(nlogn)

但代码仅通过4/12测试用例，以下是其中一个失败测试用例：

失败测试用例 #

输入：
200
998 995 995 991 989 989 984 979 968 964 955 955 947 945 942 934 933 930 928 927 918 916 905 900 898 895 895 895 892 887 882 881 878 876 872 872 858 856 846 844 839 823 808 806 804 800 799 794 793 789 784 772 766 765 764 762 762 759 757 751 747 745 738 725 720 708 706 703 699 697 693 691 690 685 682 677 662 661 656 648 642 641 640 634 632 625 623 618 618 617 601 601 600 591 585 583 578 552 550 550 546 543 539 509 505 503 503 494 486 474 472 472 472 468 467 464 439 438 434 434 427 421 420 405 399 395 392 388 386 384 377 374 368 356 350 344 342 341 337 331 298 296 296 294 290 260 259 248 245 244 244 233 228 215 211 210 206 202 201 189 186 181 178 168 163 162 161 159 151 147 143 142 142 141 139 132 130 128 125 125 120 112 111 95 92 91 88 81 69 66 63 48 44 20 18 17 14 8 1 1
20
18 31 38 126 152 170 198 199 202 243 369 376 376 408 560 572 614 665 666 942

预期结果：
177
176
176
162
153
148
144
144
142
136
119
118
118
110
89
89
83
70
70
12

我的输出：
194
193
193
179
169
164
160
160
158
152
133
132
132
124
98
98
91
77
77
15

代码问题分析 #

原二分查找逻辑存在核心错误：

1. 递归与循环混合导致逻辑混乱：binarySearch方法同时使用while循环和递归调用，mid值在递归中未重新计算，分支处理逻辑冲突。
2. 边界条件判断缺失：
   • 未处理key大于所有排行榜分数的场景（仅判断了mid-1==0的局部情况）
   • key小于所有分数时的排名计算逻辑错误
3. 排名计算偏移错误：部分分支中排名的偏移量计算不符合降序列表的排名规则。

优化方案 #

重新实现适配降序列表的二分查找，采用纯循环逻辑，简化边界判断：

• 降序列表中，若mid值大于key，则key排名在mid右侧；若mid值小于key，则key排名在mid左侧
• 循环结束后，left指针的位置即为key的插入点，排名为left+1（排名从1开始）

优化后的代码 #

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public static List<Integer> climbingLeaderboard(List<Integer> ranked, List<Integer> player) {
        List<Integer> newLeadRank = new ArrayList<>();
        List<Integer> newRankedBoard = new ArrayList<>();
        
        // 对排行榜去重（保持降序）
        if (!ranked.isEmpty()) {
            newRankedBoard.add(ranked.get(0));
            for (int i = 1; i < ranked.size(); i++) {
                if (!ranked.get(i).equals(ranked.get(i-1))) {
                    newRankedBoard.add(ranked.get(i));
                }
            }
        }
        
        // 计算每个玩家的排名
        for (int point : player) {
            newLeadRank.add(findRank(newRankedBoard, point));
        }
        return newLeadRank;
    }
    
    private static int findRank(List<Integer> sortedDesc, int key) {
        int left = 0;
        int right = sortedDesc.size() - 1;
        
        while (left <= right) {
            // 避免(left+right)整数溢出
            int mid = left + (right - left) / 2;
            int midVal = sortedDesc.get(mid);
            
            if (midVal == key) {
                return mid + 1;
            } else if (midVal > key) {
                // 降序列表，key更小，向右查找
                left = mid + 1;
            } else {
                // midVal < key，key更大，向左查找
                right = mid - 1;
            }
        }
        
        // 循环结束时，left为插入位置，排名为left+1
        return left + 1;
    }
}

代码说明 #

1. 去重逻辑优化：使用equals方法替代直接的!=，避免Integer装箱后的比较问题
2. 二分查找优化：
   • 用left + (right-left)/2计算mid，防止整数溢出
   • 适配降序列表调整指针移动方向，逻辑清晰无歧义
   • 循环结束后直接通过left指针计算排名，覆盖所有边界场景：
     • key大于所有元素：left=0，排名为1
     • key小于所有元素：left=sortedDesc.size()，排名为size+1
     • key在两个元素之间：left为插入位置，排名正确

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