How are points calculated in Reward Top K Students?

Each positive word in a report adds 3 points, and each negative word subtracts 1 point from the corresponding student's total.

Why use hash sets for positive and negative feedback words?

Hash sets allow O(1) lookup per word, ensuring scanning each report is efficient without repeatedly searching lists.

How do I resolve ties when students have the same score?

Sort students by score descending, then by student ID ascending. Lower ID wins when points are equal.

What is the primary pattern in solving this problem?

The main pattern is array scanning plus hash lookup: scan reports and check words using hash sets for scoring.

Can a student appear in multiple reports?

Yes, scores from all reports for the same student are accumulated before determining the top K students.

#2512

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

奖励最顶尖的 K 名学生

给你两个字符串数组 positive_feedback 和 negative_feedback ，分别包含表示正面的和负面的词汇。不会有单词同时是正面的和负面的。一开始，每位学生分数为 0 。每个正面的单词会给学生的分数加 3 分，每个负面的词会给学生的分数减 1 分。给你 n 个学生的…

数组哈希表字符串排序堆（优先队列）

题目描述

给你两个字符串数组 positive_feedback 和 negative_feedback ，分别包含表示正面的和负面的词汇。不会有单词同时是正面的和负面的。

一开始，每位学生分数为 0 。每个正面的单词会给学生的分数加 3 分，每个负面的词会给学生的分数减 1 分。

给你 n 个学生的评语，用一个下标从 0 开始的字符串数组 report 和一个下标从 0 开始的整数数组 student_id 表示，其中 student_id[i] 表示这名学生的 ID ，这名学生的评语是 report[i] 。每名学生的 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⁴
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⁴
report[i] 只包含小写英文字母和空格 ' ' 。
report[i] 中连续单词之间有单个空格隔开。
1 <= report[i].length <= 100
1 <= student_id[i] <= 10⁹
student_id[i] 的值 互不相同 。
1 <= k <= n

lightbulb

解题思路

方法一：哈希表 + 排序

我们可以将正面的单词存入哈希表 $ps$ 中，将负面的单词存入哈希表 $ns$ 中。

然后遍历 $report$ ，对于每个学生，我们将其得分存入数组 $arr$ 中，数组中的每个元素为一个二元组 $(t, sid)$ ，其中 $t$ 表示学生的得分，而 $sid$ 表示学生的 ID。

最后我们对数组 $arr$ 按照得分从高到低排序，如果得分相同则按照 ID 从小到大排序，然后取出前 $k$ 个学生的 ID 即可。

时间复杂度 $O(n \times \log n + (|ps| + |ns| + n) \times |s|)$ ，空间复杂度 $O((|ps|+|ns|) \times |s| + n)$ 。其中 $n$ 为学生数量， $|ps|$ 和 $|ns|$ 分别为正面和负面单词的数量， $|s|$ 为单词的平均长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

class Solution:
    def topStudents(
        self,
        positive_feedback: List[str],
        negative_feedback: List[str],
        report: List[str],
        student_id: List[int],
        k: int,
    ) -> List[int]:
        ps = set(positive_feedback)
        ns = set(negative_feedback)
        arr = []
        for sid, r in zip(student_id, report):
            t = 0
            for w in r.split():
                if w in ps:
                    t += 3
                elif w in ns:
                    t -= 1
            arr.append((t, sid))
        arr.sort(key=lambda x: (-x[0], x[1]))
        return [v[1] for v in arr[:k]]

speed

复杂度分析

指标	值
时间	complexity is O(n * m) where n is number of reports and m is average words per report, plus O(n log n) for sorting. Space complexity is O(p + q + n) for positive/negative sets and storing scores.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Checks if you use hash sets for feedback words instead of repeated list searches.
question_mark
Looks for splitting each report efficiently and tallying scores correctly.
question_mark
Validates sorting by score and breaking ties using student IDs.

warning

常见陷阱

外企场景

error
Forgetting to hash the feedback words causes slower lookups and possible timeouts.
error
Incorrectly handling ties by student ID can produce wrong top K ordering.
error
Failing to split report words correctly, miscounting points due to punctuation or spaces.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Return bottom K students instead of top K using same scoring mechanism.
arrow_right_alt
Use weighted positive and negative points for different words.
arrow_right_alt
Handle multiple reports per student with aggregation and weighted scoring.

help

常见问题

外企场景

继续练习

#2456 最流行的视频创作者 #2593 标记所有元素后数组的分数 #2418 按身高排序