3450. 一张长椅上的最多学生 🔒

题目描述

给定一个包含学生数据的 2 维数组 students，其中 students[i] = [student_id, bench_id] 表示学生 student_id 正坐在长椅 bench_id 上。

返回单个长凳上坐着的不同学生的最大数量。如果没有学生，返回 0。

注意：一个学生在输入中可以出现在同一张长椅上多次，但每个长椅上只能计算一次。

示例 1：

输入：students = [[1,2],[2,2],[3,3],[1,3],[2,3]]

输出：3

解释：

长椅 2 上有 2 个不同学生：[1, 2]。
长椅 3 上有 3 个不同学生：[1, 2, 3]。
一张长椅上不同学生的最大数量是 3。

示例 2：

输入：students = [[1,1],[2,1],[3,1],[4,2],[5,2]]

输出：3

示例：

长椅 1 上有 3 个不同学生：[1, 2, 3]。
长椅 2 上有 2 个不同学生：[4, 5]。
一张长椅上不同学生的最大数量是 3。

示例 3：

输入：students = [[1,1],[1,1]]

输出：1

解释：

一张长椅上不同学生的最大数量是 1。

示例 4：

输入：students = []

输出：0

解释：

由于不存在学生，输出为 0。

提示：

0 <= students.length <= 100
students[i] = [student_id, bench_id]
1 <= student_id <= 100
1 <= bench_id <= 100

解法

方法一：哈希表

我们用一个哈希表 \(d\) 来存储每个长椅上的学生，键为长椅编号，值为一个集合，集合中存储着该长椅上的学生编号。

遍历学生数组 \(\textit{students}\)，将学生编号和长椅编号存入哈希表 \(d\) 中。

最后，我们遍历哈希表 \(d\) 的值，取出集合的大小的最大值即为一张长椅上坐着的不同学生的最大数量。

时间复杂度 \(O(n)\)，空间复杂度 \(O(n)\)。其中 \(n\) 为学生数组 \(\textit{students}\) 的长度。

Python3JavaC++GoTypeScriptRust

class Solution:
    def maxStudentsOnBench(self, students: List[List[int]]) -> int:
        if not students:
            return 0
        d = defaultdict(set)
        for student_id, bench_id in students:
            d[bench_id].add(student_id)
        return max(map(len, d.values()))

class Solution {
    public int maxStudentsOnBench(int[][] students) {
        Map<Integer, Set<Integer>> d = new HashMap<>();
        for (var e : students) {
            int studentId = e[0], benchId = e[1];
            d.computeIfAbsent(benchId, k -> new HashSet<>()).add(studentId);
        }
        int ans = 0;
        for (var s : d.values()) {
            ans = Math.max(ans, s.size());
        }
        return ans;
    }
}

class Solution {
public:
    int maxStudentsOnBench(vector<vector<int>>& students) {
        unordered_map<int, unordered_set<int>> d;
        for (const auto& e : students) {
            int studentId = e[0], benchId = e[1];
            d[benchId].insert(studentId);
        }
        int ans = 0;
        for (const auto& s : d) {
            ans = max(ans, (int) s.second.size());
        }
        return ans;
    }
};

func maxStudentsOnBench(students [][]int) (ans int) {
    d := make(map[int]map[int]struct{})
    for _, e := range students {
        studentId, benchId := e[0], e[1]
        if _, exists := d[benchId]; !exists {
            d[benchId] = make(map[int]struct{})
        }
        d[benchId][studentId] = struct{}{}
    }
    for _, s := range d {
        ans = max(ans, len(s))
    }
    return
}

function maxStudentsOnBench(students: number[][]): number {
    const d: Map<number, Set<number>> = new Map();
    for (const [studentId, benchId] of students) {
        if (!d.has(benchId)) {
            d.set(benchId, new Set());
        }
        d.get(benchId)?.add(studentId);
    }
    let ans = 0;
    for (const s of d.values()) {
        ans = Math.max(ans, s.size);
    }
    return ans;
}

use std::collections::{HashMap, HashSet};

impl Solution {
    pub fn max_students_on_bench(students: Vec<Vec<i32>>) -> i32 {
        let mut d: HashMap<i32, HashSet<i32>> = HashMap::new();
        for e in students {
            let student_id = e[0];
            let bench_id = e[1];
            d.entry(bench_id)
                .or_insert_with(HashSet::new)
                .insert(student_id);
        }
        let mut ans = 0;
        for s in d.values() {
            ans = ans.max(s.len() as i32);
        }
        ans
    }
}

3450. 一张长椅上的最多学生 🔒

题目描述

解法

方法一：哈希表

评论