豆包MarsCode算法题：游戏排名第三大的分数

去重：将分数数组去重，得到一个不重复的分数集合。排序：对去重后的分数进行排序，按照从大到小的顺序排列。选择目标分数如果有 3 个或更多不同的分数，返回第三大的分数。如果有 2 个或更少不同的分数，返回最大的分数。

凭君语未可

1663人浏览 · 2024-11-15 09:30:00

凭君语未可 · 2024-11-15 09:30:00 发布

游戏排名第三大的分数

问题描述
思路分析
参考代码（Java）
- 代码分析

问题描述

在这里插入图片描述

思路分析

题目要求根据给定的分数数组，计算出小M的目标分数，目标分数的选择规则如下：

如果不同的分数有三个或以上，返回第三大的分数。
如果不同的分数有两个或更少，返回最大的分数。

1. 去重

由于题目提到“不同的分数”，我们首先需要从给定的分数数组中去除重复的分数，确保每个分数只出现一次。

这可以通过使用集合（比如 Set）来实现，因为集合本身会自动去除重复元素。
通过去重后，我们得到一个只包含不同分数的集合。

2. 排序

为了便于比较大小，我们需要将这些不同的分数进行排序。

排序后，分数的顺序会从小到大排列。
如果要求“第三大的分数”，则可以选择排序后的列表中倒数第三个元素。

3. 判断并返回目标分数

如果去重后的分数有三个或更多，我们需要返回第三大的分数。排序后，第三大的分数就是排在第三个位置的元素（从大到小）。
如果去重后的分数少于三个，返回最大的分数。排序后，最大的分数就是第一个元素。

4. 考虑边界情况

如果输入数组的长度很小，或者所有分数都相同，那么去重后的分数会很少（甚至为 1）。这种情况下，我们应该直接返回最大分数。
如果数组中只有 2 个或更少的不同分数，应该返回最大的分数。

总结

去重：将分数数组去重，得到一个不重复的分数集合。
排序：对去重后的分数进行排序，按照从大到小的顺序排列。
选择目标分数：
- 如果有 3 个或更多不同的分数，返回第三大的分数。
- 如果有 2 个或更少不同的分数，返回最大的分数。

时间复杂度分析：

去重操作使用 Set，插入每个元素的时间复杂度是 O(1)，因此去重整体时间复杂度是 O(n)，其中 n 是数组的长度。
排序操作的时间复杂度是 O(k log k)，其中 k 是去重后不同分数的数量。最坏情况下，k 的值最大为 n。
因此，总体的时间复杂度是 O(n + k log k)，在最坏情况下为 O(n log n)。

参考代码（Java）

import java.util.*;

public class Main {
    public static int solution(int n, int[] nums) {
        Set<Integer> uniqueScores = new HashSet<>();
        for(int score:nums){
            uniqueScores.add(score);
        }

        List<Integer> sortedScores = new ArrayList<>(uniqueScores);
        Collections.sort(sortedScores,Collections.reverseOrder());

        if(sortedScores.size()>=3){
            return sortedScores.get(2);
        }else{
            return sortedScores.get(0);
        }
    }

    public static void main(String[] args) {
        System.out.println(solution(3, new int[]{3, 2, 1}) == 1);
        System.out.println(solution(2, new int[]{1, 2}) == 2);
        System.out.println(solution(4, new int[]{2, 2, 3, 1}) == 1);
    }
}

代码分析

1. 输入处理

public static int solution(int n, int[] nums) {
    // 用set去重，得到不同的分数
    Set<Integer> uniqueScores = new HashSet<>();
    for (int score : nums) {
        uniqueScores.add(score);
    }

功能：
这段代码的目的是从输入的 nums 数组中去掉重复的分数，得到一个不重复的分数集合 uniqueScores。

HashSet<Integer> 是一个不允许重复元素的集合，因此用它来存储分数时，重复的分数会被自动过滤掉。
for (int score : nums)：这行代码通过循环遍历输入数组 nums，并把每个分数添加到 uniqueScores 集合中。因为 Set 自动去重，所以相同的分数只会出现一次。

2. 排序

    List<Integer> sortedScores = new ArrayList<>(uniqueScores);
    Collections.sort(sortedScores, Collections.reverseOrder());

功能：
这段代码的目的是将去重后的分数集合 uniqueScores 转换成 List 并按降序排序。

new ArrayList<>(uniqueScores)：将 Set 集合转换成 List，这样我们可以对它进行排序。Set 本身不支持索引访问，但 List 支持。
Collections.sort(sortedScores, Collections.reverseOrder())：使用 Collections.sort() 方法对 List 进行排序，reverseOrder() 使得排序按降序进行（即从大到小）。

3. 判断并返回目标分数

    // 根据不同分数的数量返回结果
    if (sortedScores.size() >= 3) {
        return sortedScores.get(2); // 返回第三大的分数
    } else {
        return sortedScores.get(0); // 返回最大分数
    }
}

功能：
这段代码根据排序后的不同分数的数量来决定返回哪个分数作为目标分数。

sortedScores.size() >= 3：首先判断去重后的分数是否有三个或更多。
- 如果是，返回第三大的分数，即排序后的 List 中下标为 2 的元素（因为列表是从 0 开始的）。
- 如果去重后的分数少于 3 个，则直接返回最大分数，即排序后的 List 中下标为 0 的元素。