使用Java Collections时如何优化耗时？排行榜实现超时问题求助

原代码性能瓶颈分析 #

• 循环内重复执行高开销操作：每处理一个玩家成绩，都进行了add、sort、reverse、indexOf、remove操作，其中排序的时间复杂度为O(k log k)（k为当前ranking列表长度），indexOf和remove操作的时间复杂度也为O(k)，当排行榜和玩家成绩的量级达到数千以上时，总耗时会指数级上涨。
• 存在大量冗余操作：完全不需要修改ranking列表本身，排名可以直接通过玩家成绩和已有排行榜的相对大小直接计算，插入、删除、重复排序都是完全多余的操作。

具体优化方案 #

优化后总时间复杂度可以降到O(n + m log n)，其中n是原排行榜长度，m是玩家成绩数量：

1. 预处理原排行榜：因为题目输入的ranked列表本身就是非递增排序的，直接遍历去重得到严格降序的唯一分数列表即可，不需要额外排序。
2. 采用二分查找计算排名：预处理完成后的降序列表是固定不变的，针对每个玩家成绩，直接在这个有序列表中用二分查找定位插入位置，就可以快速得到排名，不需要修改原列表。
3. 额外优化（可选）：如果输入的player列表是非递减排序的，还可以用双指针法进一步优化，从后往前遍历去重后的排行榜，逐个匹配玩家成绩，时间复杂度可以降到O(n+m)，性能更好。

优化后代码示例 #

public static List<Integer> climbingLeaderboard(List<Integer> ranked, List<Integer> player) {
    // 预处理原排行榜，去重得到严格降序的唯一分数列表
    List<Integer> uniqueRanked = new ArrayList<>();
    for (int score : ranked) {
        if (uniqueRanked.isEmpty() || !uniqueRanked.get(uniqueRanked.size() - 1).equals(score)) {
            uniqueRanked.add(score);
        }
    }
    
    List<Integer> result = new ArrayList<>();
    int n = uniqueRanked.size();
    
    // 对每个玩家成绩，用降序二分查找定位排名
    for (int pScore : player) {
        int left = 0, right = n - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (uniqueRanked.get(mid) == pScore) {
                left = mid;
                break;
            } else if (uniqueRanked.get(mid) < pScore) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        // left为插入位置，排名为left+1
        result.add(left + 1);
    }
    return result;
}

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