2512. 奖励最优秀的前 K 名学生

Medium

题目描述

给你两个字符串数组 positive_feedback 和 negative_feedback，分别包含表示正面和负面反馈的单词。注意，没有单词既是正面的又是负面的。

初始时，每个学生都有 0 分。反馈报告中的每个正面单词会使学生的分数加 3 分，而每个负面单词会使分数减 1 分。

给你 n 份反馈报告，用下标从 0 开始的字符串数组 report 和下标从 0 开始的整数数组 student_id 表示，其中 student_id[i] 表示收到反馈报告 report[i] 的学生的 ID。每个学生的 ID 都是唯一的。

给定一个整数 k，返回按分数非递增顺序排列的前 k 名学生。如果多个学生分数相同，则 ID 较小的学生排名更高。

示例 1：

输入：positive_feedback = ["smart","brilliant","studious"], negative_feedback = ["not"], report = ["this student is studious","the student is smart"], student_id = [1,2], k = 2
输出：[1,2]
解释：两个学生都有 1 个正面反馈和 3 分，但学生 1 的 ID 较小，所以排名更高。

示例 2：

输入：positive_feedback = ["smart","brilliant","studious"], negative_feedback = ["not"], report = ["this student is not studious","the student is smart"], student_id = [1,2], k = 2
输出：[2,1]
解释：
- ID 为 1 的学生有 1 个正面反馈和 1 个负面反馈，所以他有 3-1=2 分。
- ID 为 2 的学生有 1 个正面反馈，所以他有 3 分。
由于学生 2 分数更高，返回 [2,1]。

约束条件：

1 <= positive_feedback.length, negative_feedback.length <= 10^4
1 <= positive_feedback[i].length, negative_feedback[j].length <= 100
positive_feedback[i] 和 negative_feedback[j] 都由小写英文字母组成
没有单词同时出现在 positive_feedback 和 negative_feedback 中
n == report.length == student_id.length
1 <= n <= 10^4
report[i] 由小写英文字母和空格组成
report[i] 中连续的单词之间有一个空格
1 <= report[i].length <= 100
1 <= student_id[i] <= 10^9
student_id[i] 的所有值都是唯一的
1 <= k <= n

解题思路

这是一个典型的数据处理和排序问题。主要思路如下：

预处理反馈词汇：将正面和负面反馈词汇分别存储在哈希表中，便于快速查找。
计算学生得分：
- 遍历每份反馈报告，将其分割成单词
- 对每个单词，检查是否在正面反馈词汇中（加3分）或负面反馈词汇中（减1分）
- 累计每个学生的总得分
排序选择：
- 创建包含学生ID和得分的数据结构
- 按照题目要求排序：首先按得分降序，得分相同时按学生ID升序
- 取前k名学生

排序规则需要特别注意：当两个学生分数相同时，ID较小的学生排名更高。

时间复杂度主要来自于处理所有反馈报告中的单词和最后的排序操作。空间复杂度主要用于存储反馈词汇的哈希表和学生得分信息。

代码实现

class Solution {
public:
    vector<int> topStudents(vector<string>& positive_feedback, vector<string>& negative_feedback, vector<string>& report, vector<int>& student_id, int k) {
        unordered_set<string> positive(positive_feedback.begin(), positive_feedback.end());
        unordered_set<string> negative(negative_feedback.begin(), negative_feedback.end());
        
        vector<pair<int, int>> students; // {score, student_id}
        
        for (int i = 0; i < report.size(); i++) {
            int score = 0;
            stringstream ss(report[i]);
            string word;
            
            while (ss >> word) {
                if (positive.count(word)) {
                    score += 3;
                } else if (negative.count(word)) {
                    score -= 1;
                }
            }
            
            students.push_back({score, student_id[i]});
        }
        
        sort(students.begin(), students.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
            if (a.first == b.first) {
                return a.second < b.second; // lower ID ranks higher
            }
            return a.first > b.first; // higher score ranks higher
        });
        
        vector<int> result;
        for (int i = 0; i < k; i++) {
            result.push_back(students[i].second);
        }
        
        return result;
    }
};

class Solution:
    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int) -> List[int]:
        positive_set = set(positive_feedback)
        negative_set = set(negative_feedback)
        
        students = []
        
        for i in range(len(report)):
            score = 0
            words = report[i].split()
            
            for word in words:
                if word in positive_set:
                    score += 3
                elif word in negative_set:
                    score -= 1
            
            students.append((score, student_id[i]))
        
        # Sort by score (descending), then by student_id (ascending)
        students.sort(key=lambda x: (-x[0], x[1]))
        
        return [students[i][1] for i in range(k)]

public class Solution {
    public IList<int> TopStudents(string[] positive_feedback, string[] negative_feedback, string[] report, int[] student_id, int k) {
        var positiveSet = new HashSet<string>(positive_feedback);
        var negativeSet = new HashSet<string>(negative_feedback);
        
        var students = new List<(int score, int id)>();
        
        for (int i = 0; i < report.Length; i++) {
            int score = 0;
            string[] words = report[i].Split(' ');
            
            foreach (string word in words) {
                if (positiveSet.Contains(word)) {
                    score += 3;
                } else if (negativeSet.Contains(word)) {
                    score -= 1;
                }
            }
            
            students.Add((score, student_id[i]));
        }
        
        students.Sort((a, b) => {
            if (a.score == b.score) {
                return a.id.CompareTo(b.id); // lower ID ranks higher
            }
            return b.score.CompareTo(a.score); // higher score ranks higher
        });
        
        var result = new List<int>();
        for (int i = 0; i < k; i++) {
            result.Add(students[i].id);
        }
        
        return result;
    }
}

/**
 * @param {string[]} positive_feedback
 * @param {string[]} negative_feedback
 * @param {string[]} report
 * @param {number[]} student_id
 * @param {number} k
 * @return {number[]}
 */
var topStudents = function(positive_feedback, negative_feedback, report, student_id, k) {
    const positiveSet = new Set(positive_feedback);
    const negativeSet = new Set(negative_feedback);
    
    const students = [];
    
    for (let i = 0; i < report.length; i++) {
        const words = report[i].split(' ');
        let points = 0;
        
        for (const word of words) {
            if (positiveSet.has(word)) {
                points += 3;
            } else if (negativeSet.has(word)) {
                points -= 1;
            }
        }
        
        students.push({
            id: student_id[i],
            points: points
        });
    }
    
    students.sort((a, b) => {
        if (a.points !== b.points) {
            return b.points - a.points;
        }
        return a.id - b.id;
    });
    
    return students.slice(0, k).map(student => student.id);
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	复杂度	说明
时间复杂度	O(W + N log N)	W是所有报告中的单词总数，N是学生数量，排序需要O(N log N)
空间复杂度	O(P + G + N)	P是正面反馈词汇数，G是负面反馈词汇数，N是学生数量

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目