印刷网站建设价格,河北邯郸有几个区县,北京装饰装修公司,选择响应式网站优先队列哈希集合反向思维(或自定义排序)
模拟#xff0c;请直接看算法思路#xff1a; 两个哈希集合S1和S2, S1存正面词汇#xff0c;S2存负面词汇#xff1b;一个优先队列pq#xff0c;pq存{score, id}键值对#xff0c;即学生分数-学生id。
算法流程#xff1a;
初…优先队列哈希集合反向思维(或自定义排序)
模拟请直接看算法思路 两个哈希集合S1和S2, S1存正面词汇S2存负面词汇一个优先队列pqpq存{score, id}键值对即学生分数-学生id。
算法流程
初始化S1和S2遍历reportreport里存的是句子每个句子report[i]对应一个学生student_id[i]的评价抠出句子的每个单词report[i][j]将单词分数(对照哈希集合)加给学生。上述流程确定了学生student_id[i]的分数将学生分数加入优先队列。记录前k个学生id存入答案数组ansans即为所求。
请注意优先队列默认大根堆按fisrt成员从大到小排序在first成员相等时按照second成员从大到小排序。score是first成员id是second成员出现矛盾当score相同时题目要求id从小到大排序。解决方法1. 将score变为负数或将id变为负数。2. 自定义排序规则(优先队列)本题解将score变为负数解决了矛盾。
class Solution {
public:vectorint topStudents(vectorstring positive_feedback, vectorstring negative_feedback, vectorstring report, vectorint student_id, int k) {// 哈希集合unordered_setstring S1, S2;vectorint ans vectorint (k, 0); // 保存答案的ans顺序priority_queue pairint, int, vectorpairint,int pq; // 存{score, id}键值对。for (int i 0; i positive_feedback.size(); i ) {S1.insert(positive_feedback[i]);}for (int i 0; i negative_feedback.size(); i ) {S2.insert(negative_feedback[i]);}for (int i 0; i report.size(); i ) {int j 0; // 遍历report[i];int score 0, id student_id[i];while (j report[i].size()) {string t ;while (j report[i].size() report[i][j] ! ) {t report[i][j ];}j ;if (S1.count(t)) score - 3; // 得分数值变小else if (S2.count(t)) score ; // 扣分数值变大}pq.push({score, id});if (pq.size() k) pq.pop();}int i k - 1;while (i 0) { // while (pq.size() i 0) {int id pq.top().second;pq.pop();ans[i --] id;}return ans;}
};时间复杂度 O ( n l o g k ) O(nlogk) O(nlogk) : n n n是 r e p o r t report report的长度 k k k 是常数(奖励最顶尖的前k名学生)优先队列内部最多维护 k 1 k1 k1名学生一共 n n n名学生进一次优先队列最多 n n n名学生出一次优先队列时间复杂度 O ( n l o g k ) O(nlogk) O(nlogk)。 空间复杂度 O ( n ) O(n) O(n) : 两个哈希集合/ans数组的空间复杂度 O ( n ) O(n) O(n)优先队列的最坏空间复杂度 O ( k ) O(k) O(k)总体空间复杂度 O ( n ) O(n) O(n) 。
AC 致语
理解思路很重要。请读者放心留言可以是疑惑的点或者感谢/夸奖也可以墨染看到会回复的。
