奖励最顶尖的 K 名学生

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 top k 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 <= 104
• 1 <= positive_feedback[i].length, negative_feedback[j].length <= 100
• Both positive_feedback[i] and negative_feedback[j] consists of lowercase English letters.
• No word is present in both positive_feedback and negative_feedback.
• n == report.length == student_id.length
• 1 <= n <= 104
• report[i] consists of lowercase English letters and spaces ' '.
• There is a single space between consecutive words of report[i].
• 1 <= report[i].length <= 100
• 1 <= student_id[i] <= 109
• All the values of student_id[i] are unique.
• 1 <= k <= n

/*
思路：
1. 使用Java Streams操作数据。
2. 创建两个集合存储正面和负面的词汇。
3. 对每个学生的评语进行流操作，计算每个学生的得分。
4. 使用Comparator根据得分和ID进行排序。
5. 获取前k个学生的ID。
*/

import java.util.*;
import java.util.stream.*;

public class Solution {
    public List<Integer> topStudents(String[] positive_feedback, String[] negative_feedback, String[] report, int[] student_id, int k) {
        Set<String> positiveWords = new HashSet<>(Arrays.asList(positive_feedback));
        Set<String> negativeWords = new HashSet<>(Arrays.asList(negative_feedback));

        return IntStream.range(0, report.length)
            .mapToObj(i -> new int[]{student_id[i], calculateScore(report[i], positiveWords, negativeWords)})
            .sorted((a, b) -> b[1] != a[1] ? Integer.compare(b[1], a[1]) : Integer.compare(a[0], b[0]))
            .limit(k)
            .map(a -> a[0])
            .collect(Collectors.toList());
    }

    private int calculateScore(String report, Set<String> positiveWords, Set<String> negativeWords) {
        return Arrays.stream(report.split(" "))
            .mapToInt(word -> positiveWords.contains(word) ? 3 : (negativeWords.contains(word) ? -1 : 0))
            .sum();
    }
}

此题解采用的方法是：首先将正面反馈词汇和负面反馈词汇存入集合中，方便快速查找。对于每个学生的评语，通过分割字符串获取到评语中的每个单词，然后判断这些单词是否存在于正面或负面词汇的集合中，根据匹配结果更新学生的得分。最后，将学生根据得分从高到低排序，得分相同则按ID升序排序。最终返回得分最高的k名学生的ID。

O(n*m + n log n)

O(p+q+n)