2512. 奖励最顶尖的 K 名学生
2512. 奖励最顶尖的 K 名学生
🟠 🔖 数组 哈希表 字符串 排序 堆（优先队列） 🔗 力扣 LeetCode
题目
You are given two string arrays positive_feedback and negative_feedback, containing the words denoting positive and negative feedback, respectively. Note that no word is both positive and negative.
Initially every student has 0 points. Each positive word in a feedback report increases the points of a student by 3, whereas each negative word decreases the points by 1.
You are given n feedback reports, represented by a 0-indexed string array report and a 0-indexed integer array student_id, where student_id[i] represents the ID of the student who has received the feedback report report[i]. The ID of each student is unique.
Given an integer k, return the topk students after ranking them in non-increasing order by their points. In case more than one student has the same points, the one with the lower ID ranks higher.
Example 1:
Input: positive_feedback = ["smart","brilliant","studious"], negative_feedback = ["not"], report = ["this student is studious","the student is smart"], student_id = [1,2], k = 2
Output: [1,2]
Explanation:
Both the students have 1 positive feedback and 3 points but since student 1 has a lower ID he ranks higher.
Example 2:
Input: positive_feedback = ["smart","brilliant","studious"], negative_feedback = ["not"], report = ["this student is not studious","the student is smart"], student_id = [1,2], k = 2
Output: [2,1]
Explanation:
- The student with ID 1 has 1 positive feedback and 1 negative feedback, so he has 3-1=2 points.
- The student with ID 2 has 1 positive feedback, so he has 3 points.
Since student 2 has more points, [2,1] is returned.
Constraints:
1 <= positive_feedback.length, negative_feedback.length <= 10^41 <= positive_feedback[i].length, negative_feedback[j].length <= 100- Both
positive_feedback[i]andnegative_feedback[j]consists of lowercase English letters. - No word is present in both
positive_feedbackandnegative_feedback. n == report.length == student_id.length1 <= n <= 10^4report[i]consists of lowercase English letters and spaces' '.- There is a single space between consecutive words of
report[i]. 1 <= report[i].length <= 1001 <= student_id[i] <= 10^9- All the values of
student_id[i]are unique. 1 <= k <= 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^41 <= positive_feedback[i].length, negative_feedback[j].length <= 100positive_feedback[i]和negative_feedback[j]都只包含小写英文字母。positive_feedback和negative_feedback中不会有相同单词。n == report.length == student_id.length1 <= n <= 10^4report[i]只包含小写英文字母和空格' '。report[i]中连续单词之间有单个空格隔开。1 <= report[i].length <= 1001 <= student_id[i] <= 10^9student_id[i]的值 互不相同 。1 <= k <= n
解题思路
- 数据预处理
- 题目给定
positive_feedback和negative_feedback两个字符串数组，我们使用Set来存储这些关键词，以便在查找时O(1)判断某个单词是否属于正面或负面反馈。
- 计算得分
- 遍历
report数组，每个report[i]代表student_id[i]的评论内容：- 将
report[i]按空格拆分成单词数组words。 - 依次判断
words中的每个单词：- 若单词在
positive_feedback中，得分+3。 - 若单词在
negative_feedback中，得分-1。
- 若单词在
- 计算完毕后，得到
student_id[i]的最终得分score。
- 将
- 维护最小堆
- 由于题目要求找到分数最高的
k个学生，并按照得分降序、相同得分按学号升序排序，因此我们需要维护一个最小堆，存储当前前k名的[score, student_id]：- 堆的比较方式：
score小的排在堆顶，优先移除。- 若
score相同，student_id大的排在堆顶，优先移除。
- 堆的操作：
- 当
heap.size() < k时，直接插入[score, student_id]。 - 当
heap.size() == k时：- 若
heap.peek()[0] < score（新学生得分更高），则弹出堆顶元素，插入新元素。 - 若
heap.peek()[0] === score且heap.peek()[1] > student_id（相同得分但学号更小），则仍然弹出堆顶元素，插入新元素。
- 若
- 当
- 堆的比较方式：
- 取出前
k名学生并排序
- 由于堆中存的是
k个最优学生，按score升序存储（因为是最小堆）。 - 依次
pop()取出student_id，然后反转数组，得到按得分降序、学号升序的排序结果。
复杂度分析
- 时间复杂度：
O(nm + k log n)- 维护最小堆：
O(n * log k)（其中n是student_id的长度） - 计算得分时间：
O(n * m)（m是report[i]的平均长度） - 取前 K 个时间：
O(k log k) - 总时间复杂度：
O(nm + (k + n) * log k)
- 维护最小堆：
- 空间复杂度：
O(P + N + k)positive_feedback和negative_feedback使用Set存储，O(P + N)。- 堆最多存储
k个元素，O(k)。 - 额外的结果数组
O(k)。
代码
/**
* @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
) {
// 将正面和负面反馈单词存入 Set
const positive = new Set(positive_feedback);
const negative = new Set(negative_feedback);
// 最小堆，按得分升序排序，得分相同按 student_id 降序
const heap = new MinHeap([], (a, b) =>
a[0] === b[0] ? b[1] < a[1] : a[0] < b[0]
);
for (let i = 0; i < report.length; i++) {
let score = 0;
const words = report[i].split(' ');
for (let word of words) {
if (positive.has(word)) {
score += 3;
} else if (negative.has(word)) {
score -= 1;
}
}
// 只存前 k 个学生
if (heap.size() < k) {
heap.insert([score, student_id[i]]);
} else if (
heap.peek()[0] < score ||
(heap.peek()[0] === score && heap.peek()[1] > student_id[i])
) {
heap.pop();
heap.insert([score, student_id[i]]);
}
}
const res = [];
while (!heap.isEmpty()) {
res.push(heap.pop()[1]);
}
return res.reverse(); // 从最低分到最高分，翻转得到最终结果
};
// 最小优先队列
class MinHeap {
constructor(arr = [], priority = (a, b) => a < b) {
this.heap = arr;
this.priority = priority;
for (let i = Math.floor(this.heap.length / 2) - 1; i >= 0; i--) {
this.heapifyDown(i);
}
}
insert(num) {
this.heap.push(num);
this.heapifyUp(this.heap.length - 1);
}
pop() {
if (this.heap.length === 0) return null;
const top = this.heap[0];
const last = this.heap.pop();
if (this.heap.length > 0) {
this.heap[0] = last;
this.heapifyDown(0);
}
return top;
}
isEmpty() {
return this.heap.length == 0;
}
size() {
return this.heap.length;
}
peek() {
return this.heap[0];
}
heapifyDown(i) {
const n = this.heap.length;
const left = 2 * i + 1;
const right = 2 * i + 2;
let smallest = i;
if (left < n && this.priority(this.heap[left], this.heap[smallest])) {
smallest = left;
}
if (right < n && this.priority(this.heap[right], this.heap[smallest])) {
smallest = right;
}
if (smallest !== i) {
[this.heap[i], this.heap[smallest]] = [this.heap[smallest], this.heap[i]];
this.heapifyDown(smallest);
}
}
heapifyUp(i) {
while (i > 0) {
const parent = Math.floor((i - 1) / 2);
if (this.priority(this.heap[i], this.heap[parent])) {
[this.heap[i], this.heap[parent]] = [this.heap[parent], this.heap[i]];
i = parent;
} else {
break;
}
}
}
}
相关题目
| 题号 | 标题 | 题解 | 标签 | 难度 | 力扣 |
|---|---|---|---|---|---|
| 406 | 根据身高重建队列 | [✓] | 树状数组 线段树 数组 1+ | 🟠 | 🀄️ 🔗 |
| 2146 | 价格范围内最高排名的 K 样物品 | 广度优先搜索 数组 矩阵 2+ | 🟠 | 🀄️ 🔗 |