2023.10.11 leetcode-2512 奖励最顶尖的k名学生

题目

• 给你两个字符串数组 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 <= 104
  • 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 <= 104
  • report[i] 只包含小写英文字母和空格 ‘ ‘ 。
  • report[i] 中连续单词之间有单个空格隔开。
  • 1 <= report[i].length <= 100
  • 1 <= student_id[i] <= 109
  • student_id[i] 的值 互不相同 。
  • 1 <= k <= n

---

分析

• 根据题目可知，学生评分取决于report中postive_feedback单词和negative_feedback单词的出现次数。同时可知report中的每个单词被空格拆分，故可得大致解法 -> 统计每个report中的关键词数量并转换为分数。
• 在提示中可以知道，student_id[i]的值互不相同，故每个student[i]和一个report[i]对应，一次可以用一个数组直接建立联系，无需使用哈希表建立映射和判重。
• 为了加快关键字匹配速度，可以使用集合进行关键字存在性判断。

---

代码实现

class Solution {
    // 暴力匹配
    // 用hash存储关键字，遍历评价列表，获取学生评价，后进行排序获取前k个值
    // 时间复杂度O(nlogn) 空间复杂度O(n)
    public List<Integer> topStudents(String[] positive_feedback, String[] negative_feedback, String[] report, int[] student_id, int k) {
        //两个set，存放关键字，加速匹配
        HashSet<String> pos_set = new HashSet<>();
        HashSet<String> neg_set = new HashSet<>();
        //优先队列，获得前k个学生
        PriorityQueue<Integer[]> queue = new PriorityQueue<>(new Comparator<Integer[]>() {
            public int compare(Integer[] a,Integer[] b)
            {
                if(a[1]==b[1])
                    return a[0]-b[0];
                return b[1]-a[1];
            }
        });
        // 返回值
        List<Integer> ans = new ArrayList<>();
        for(int i = 0;i<positive_feedback.length;++i)
            pos_set.add(positive_feedback[i]);
        for(int i = 0;i<negative_feedback.length;++i)
            neg_set.add(negative_feedback[i]);
        for(int i = 0;i<report.length;++i)
        {
            String cur[] = report[i].split(" ");//report单词划分，提取关键字
            int num = 0;
            for(int j = 0;j<cur.length;++j)
            {
                if(pos_set.contains(cur[j]))
                    num+=3;
                else if(neg_set.contains(cur[j]))
                    num-=1;
            }
            queue.offer(new Integer[]{student_id[i],num});
        }
        for(int i = 0;i<k;++i)
            ans.add(queue.poll()[0]);
        return ans;
    }
}

---