rust 解法, 执行用时: 28 ms, 内存消耗: 6.1 MB, 提交时间: 2023-10-11 07:38:47

use std::cmp::Ordering;
use std::collections::HashMap;

impl Solution {
    pub fn top_students(positive_feedback: Vec<String>, negative_feedback: Vec<String>, report: Vec<String>, student_id: Vec<i32>, k: i32) -> Vec<i32> {
        struct Student(i32, i32);
        let mut students = Vec::new();
        // 需要用 HashMap 预处理, 否则会超时
        let mut map = HashMap::with_capacity(positive_feedback.len() + negative_feedback.len());
        for p in positive_feedback {
            map.insert(p, 3);
        }
        for ne in negative_feedback {
            map.insert(ne, -1);
        }
        for (i, s) in student_id.iter().enumerate() {
            let mut rank = 0;
            let report_i: &String = &report[i];
            for r in report_i.split_whitespace() {
                if let Some(m) = map.get(r) {
                    rank += *m;
                }
            }
            students.push(Student(*s, rank));
        }

        students.sort_by(|a, b| {
            match b.1.cmp(&a.1) {
                Ordering::Greater => Ordering::Greater,
                Ordering::Less => Ordering::Less,
                Ordering::Equal => a.0.cmp(&b.0)
            }
        });

        let mut result = vec![0; k as usize];
        for i in 0..k as usize {
            result[i] = students[i].0;
        }
        result
    }
}

javascript 解法, 执行用时: 232 ms, 内存消耗: 68 MB, 提交时间: 2023-10-11 07:37:59

/**
 * @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 words = {};
	for (const word of positive_feedback) {
		words[word] = 3;
	}
	for (const word of negative_feedback) {
		words[word] = -1;
	}
	const A = [];
	for (let i = 0; i < report.length; i++) {
		let score = 0;
		for (const word of report[i].split(" ")) {
			score += words[word] || 0;
		}
		A.push([-score, student_id[i]]);
	}

	A.sort((a, b) => a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
	return A.slice(0, k).map(([, i]) => i);
};

java 解法, 执行用时: 60 ms, 内存消耗: 53.3 MB, 提交时间: 2023-10-11 07:37:39

class Solution {
    public List<Integer> topStudents(String[] positive_feedback, String[] negative_feedback, String[] report, int[] student_id, int k) {
        Map<String, Integer> words = new HashMap<>();
        for (String word : positive_feedback) {
            words.put(word, 3);
        }
        for (String word : negative_feedback) {
            words.put(word, -1);
        }
        int n = report.length;
        int[] scores = new int[n];
        int[][] A = new int[n][2];
        for (int i = 0; i < n; i++) {
            int score = 0;
            for (String word : report[i].split(" ")) {
                score += words.getOrDefault(word, 0);
            }
            A[i] = new int[]{-score, student_id[i]};
        }
        Arrays.sort(A, (a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
        List<Integer> topK = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            topK.add(A[i][1]);
        }
        return topK;
    }
}

cpp 解法, 执行用时: 268 ms, 内存消耗: 90 MB, 提交时间: 2023-10-11 07:37:25

class Solution {
public:
    vector<int> topStudents(vector<string>& positive_feedback, vector<string>& negative_feedback, vector<string>& report, vector<int>& student_id, int k) {
        unordered_map<std::string, int> words;
        for (const auto& word : positive_feedback) {
            words[word] = 3;
        }
        for (const auto& word : negative_feedback) {
            words[word] = -1;
        }
        vector<vector<int>> A;
        for (int i = 0; i < report.size(); i++) {
            stringstream ss; //stream根据空格分词
            string w;
            int score = 0;
            ss << report[i];
            while (ss >> w) {
                if (words.count(w)) {
                    score += words[w];
                }
            }
            A.push_back({-score, student_id[i]});
        }
        sort(A.begin(), A.end());
        vector<int> top_k;
        for (int i = 0; i < k; i++) {
            top_k.push_back(A[i][1]);
        }
        return top_k;
    }
};

python3 解法, 执行用时: 124 ms, 内存消耗: 21.8 MB, 提交时间: 2022-12-25 12:01:40

class Solution:
    def topStudents(self, positive_feedback: list[str], negative_feedback: list[str], report: list[str],
                    student_id: list[int], k: int) -> list[int]:
        h = list()
        positive_feedback = set(positive_feedback)
        negative_feedback = set(negative_feedback)
        for r, idx in zip(report, student_id):
            cnt = 0
            for word in r.split():
                if word in positive_feedback:
                    cnt += 3
                elif word in negative_feedback:
                    cnt += -1
            heappush(h, (-cnt, idx))
        
        res = list()
        while k:
            res.append(heappop(h)[1])
            k -= 1
        return res

golang 解法, 执行用时: 104 ms, 内存消耗: 10 MB, 提交时间: 2022-12-25 12:01:00

func topStudents(positiveFeedback, negativeFeedback, report []string, studentId []int, k int) []int {
	score := map[string]int{}
	for _, w := range positiveFeedback {
		score[w] = 3
	}
	for _, w := range negativeFeedback {
		score[w] = -1
	}
	type pair struct{ score, id int }
	a := make([]pair, len(report))
	for i, r := range report {
		s := 0
		for _, w := range strings.Split(r, " ") {
			s += score[w]
		}
		a[i] = pair{s, studentId[i]}
	}
	sort.Slice(a, func(i, j int) bool {
		a, b := a[i], a[j]
		return a.score > b.score || a.score == b.score && a.id < b.id
	})
	ans := make([]int, k)
	for i, p := range a[:k] {
		ans[i] = p.id
	}
	return ans
}

python3 解法, 执行用时: 156 ms, 内存消耗: 24.7 MB, 提交时间: 2022-12-25 12:00:43

'''
把 feedback 及其分数存到哈希表 score 中，对每个 reporti，按照空格分割，然后用 score 计算分数之和。
最后按照题目规则排序，取前 k 个 studentId 为答案。
'''
class Solution:
    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int) -> List[int]:
        score = defaultdict(int)
        for w in positive_feedback: score[w] = 3
        for w in negative_feedback: score[w] = -1
        a = sorted((-sum(score[w] for w in r.split()), i) for r, i in zip(report, student_id))
        return [i for _, i in a[:k]]