华为OD机试 - 查找舆情热词（Python/JS/C/C++ 2024 C卷 100分）

在这里插入图片描述

华为OD机试 2024E卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试真题（Python/JS/C/C++）》。

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新。

一、题目描述

网上新闻越来越多，希望对新闻进行热词处理并归类，方便获取信息，现在已经将每篇文章处理为2个字符串，即一个标题，一个正文串，字符串中使用“ ”作为分隔符进行分词。

M篇新闻按照新闻发布的先后顺序处理完并输入，现在希望对所有新闻中出现的词语进行处理，输出出现频率最高的topN个词语，作为热词。标题中出现的词语频率系数为3，正文中出现的词语频率系数为1；返回的答案按照词语出现频率由高到低排序，当词语出现的频率相同时，在标题中出现的频率次数高的排在前面；如果仍然相同，则按照词语在标题中出现的先后顺序进行排序，先出现的排在前面；如果仍然相同，则按照词语在正文中出现的先后顺序进行排序，先出现的排在前面。

二、输入描述

第一行输入为正整数topN和文章数M，即要输出的出现频率最高的词语的个数和处理文章的数量，由于每篇文章被处理为标题和正文2行，因此后面有2 * M行数据。

从第二行起，是按顺序处理后每篇文章的标题串和正文串，即第二行是第一篇文章的标题串，第三行是第一篇文章的正文串，第四行是第二篇文章的标题串，第五行是第二篇文章的正文串，以此类推。

三、输出描述

使用一行输出出现频率最高的topN个词语，每个词语以“ ”隔开。

四、测试用例

测试用例1

1、输入

3 2
xinguan feiyan xinzeng bendi quezhen anli
ju baodao chengdu xinzeng xinguan feiyan bendi quezhen anli yili shenzhen xinzeng bendi quezhen anli liangli yiqing zhhengti kongzhi lianghao
xinguan yimiao linchuang shiyan
wuzhong xinguan yimiao tongguo sanqi linchuang shiyan xiaoguo lianghao

2、输出

xinguan xinzeng bendi

测试用例2

1、输入

3 2
nezha1 nezha2 nezha10 nezha4 nezha5 nezha6
nezha1 nezha2 nezha3 nezha4 nezha4 nezha6 nezha1 nezha2 nezha3 nezha5 nezha6
nezha1 nezha7 nezha8 nezha9 nezha4 nezha10
nezha1 nezha7 nezha8 nezha9 nezha10 nezha11 nezha1 nezha7 nezha8 nezha9 nezha10 nezha11

2、输出

nezha1 nezha10 nezha4

四、解题思路

题目描述就是解题思路：

标题中出现的词语频率系数为3，正文中出现的词语频率系数为1；
返回的答案按照词语出现频率由高到低排序
当词语出现的频率相同时，在标题中出现的频率次数高的排在前面；
如果仍然相同，则按照词语在标题中出现的先后顺序进行排序，先出现的排在前面；
如果仍然相同，则按照词语在正文中出现的先后顺序进行排序，先出现的排在前面。

六、Python算法源码

import sys
from collections import defaultdictdef main():# 读取第一行输入first_line = sys.stdin.readline().strip().split()topN = int(first_line[0])M = int(first_line[1])map_freq = defaultdict(int)       # 总词频title_map = defaultdict(int)      # 标题词频content_map = defaultdict(int)    # 正文词频arr_list = []                      # 存储所有标题和正文# 读取每篇文章的标题和正文for i in range(M * 2):line = sys.stdin.readline().strip().split()arr_list.append(line)if i % 2 == 0:  # 标题for word in line:title_map[word] += 3    # 标题词频增加3map_freq[word] += 3      # 总词频增加3else:            # 正文for word in line:content_map[word] += 1    # 正文词频增加1map_freq[word] += 1       # 总词频增加1# 将词频转换为列表以便排序list_freq = list(map_freq.items())# 自定义排序函数def compare(item):word, freq = itemreturn (-freq, -title_map[word], get_first_occurrence(arr_list, word, True), get_first_occurrence(arr_list, word, False))# 获取词语在标题或正文中首次出现的位置def get_first_occurrence(arr_list, word, is_title):start = 0 if is_title else 1step = 2for i in range(start, len(arr_list), step):for w in arr_list[i]:if w == word:return ireturn float('inf')  # 如果未出现，返回无限大# 排序list_freq.sort(key=compare)# 取前topN个词语result = [word for word, freq in list_freq[:topN]]# 输出结果print(' '.join(result))if __name__ == "__main__":main()

七、JavaScript算法源码

const readline = require('readline');function main() {const rl = readline.createInterface({input: process.stdin,output: process.stdout});let input = [];rl.on('line', (line) => {input.push(line.trim());});rl.on('close', () => {let firstLine = input[0].split(' ').map(Number);let topN = firstLine[0];let M = firstLine[1];let mapFreq = new Map();      // 总词频let titleMap = new Map();     // 标题词频let contentMap = new Map();   // 正文词频let arrList = [];             // 存储所有标题和正文for (let i = 0; i < M * 2; i++) {let words = input[1 + i].split(' ');arrList.push(words);if (i % 2 === 0) { // 标题for (let word of words) {titleMap.set(word, (titleMap.get(word) || 0) + 3);mapFreq.set(word, (mapFreq.get(word) || 0) + 3);}} else { // 正文for (let word of words) {contentMap.set(word, (contentMap.get(word) || 0) + 1);mapFreq.set(word, (mapFreq.get(word) || 0) + 1);}}}// 将Map转换为数组let listFreq = Array.from(mapFreq.entries());// 自定义排序listFreq.sort((a, b) => {// 按总频率降序if (b[1] !== a[1]) return b[1] - a[1];// 按标题频率降序let titleA = titleMap.get(a[0]) || 0;let titleB = titleMap.get(b[0]) || 0;if (titleB !== titleA) return titleB - titleA;// 按标题中先出现的顺序let order = getFirstOccurrence(arrList, a[0], true) - getFirstOccurrence(arrList, b[0], true);if (order !== 0) return order;// 按正文中先出现的顺序return getFirstOccurrence(arrList, a[0], false) - getFirstOccurrence(arrList, b[0], false);});// 获取前topN个词语let result = [];for (let i = 0; i < Math.min(topN, listFreq.length); i++) {result.push(listFreq[i][0]);}// 输出结果console.log(result.join(' '));});/*** 获取词语在标题或正文中首次出现的位置* @param {Array} arrList 所有标题和正文* @param {String} word 词语* @param {Boolean} isTitle 是否在标题中查找* @returns {Number} 位置索引*/function getFirstOccurrence(arrList, word, isTitle) {let start = isTitle ? 0 : 1;for (let i = start; i < arrList.length; i += 2) {for (let w of arrList[i]) {if (w === word) return i;}}return Infinity; // 未出现}
}main();

八、C算法源码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>#define MAX_WORDS 10000
#define MAX_LEN 100typedef struct {char word[MAX_LEN];int total_freq;int title_freq;int first_title;int first_content;
} WordInfo;// 比较函数
int compare(const void *a, const void *b) {WordInfo *w1 = (WordInfo *)a;WordInfo *w2 = (WordInfo *)b;// 按总频率降序if (w2->total_freq != w1->total_freq)return w2->total_freq - w1->total_freq;// 按标题频率降序if (w2->title_freq != w1->title_freq)return w2->title_freq - w1->title_freq;// 按标题中先出现的顺序if (w1->first_title != w2->first_title)return w1->first_title - w2->first_title;// 按正文中先出现的顺序return w1->first_content - w2->first_content;
}int main(){int topN, M;scanf("%d %d", &topN, &M);char buffer[10000][MAX_LEN];int count = 0;WordInfo words[MAX_WORDS];int word_count = 0;for(int i = 0; i < M * 2; i++){scanf(" %[^\n]", buffer[i]);char *token = strtok(buffer[i], " ");while(token != NULL){// 查找是否已存在int found = -1;for(int j = 0; j < word_count; j++){if(strcmp(words[j].word, token) == 0){found = j;break;}}if(found == -1){strcpy(words[word_count].word, token);words[word_count].total_freq = 0;words[word_count].title_freq = 0;words[word_count].first_title = -1;words[word_count].first_content = -1;found = word_count;word_count++;}// 更新频率if(i % 2 == 0){ // 标题words[found].total_freq += 3;words[found].title_freq += 3;if(words[found].first_title == -1){words[found].first_title = i /2;}}else{ // 正文words[found].total_freq +=1;if(words[found].first_content == -1){words[found].first_content = i /2;}}token = strtok(NULL, " ");}}// 排序qsort(words, word_count, sizeof(WordInfo), compare);// 输出前topN个词语for(int i = 0; i < topN && i < word_count; i++){printf("%s ", words[i].word);}printf("\n");return 0;
}

九、C++算法源码

#include <bits/stdc++.h>
using namespace std;struct WordInfo {string word;int total_freq;int title_freq;int first_title;int first_content;
};int main(){int topN, M;cin >> topN >> M;cin.ignore(); // 忽略换行符vector<vector<string>> arrList;unordered_map<string, WordInfo> wordMap;int word_count = 0;for(int i = 0; i < M *2; i++){string line;getline(cin, line);vector<string> words;string word;stringstream ss(line);while(ss >> word){words.push_back(word);if(wordMap.find(word) == wordMap.end()){WordInfo wi;wi.word = word;wi.total_freq = 0;wi.title_freq = 0;wi.first_title = -1;wi.first_content = -1;wordMap[word] = wi;}if(i %2 ==0){ // 标题wordMap[word].total_freq +=3;wordMap[word].title_freq +=3;if(wordMap[word].first_title == -1){wordMap[word].first_title = arrList.size();}}else{ // 正文wordMap[word].total_freq +=1;if(wordMap[word].first_content == -1){wordMap[word].first_content = arrList.size();}}}arrList.push_back(words);}// 转换为vectorvector<WordInfo> words;for(auto &p: wordMap){words.push_back(p.second);}// 排序sort(words.begin(), words.end(), [&](const WordInfo &a, const WordInfo &b) -> bool{if(a.total_freq != b.total_freq)return a.total_freq > b.total_freq;if(a.title_freq != b.title_freq)return a.title_freq > b.title_freq;if(a.first_title != b.first_title)return a.first_title < b.first_title;return a.first_content < b.first_content;});// 输出前topN个词语for(int i =0; i < topN && i < words.size(); i++){cout << words[i].word;if(i != topN-1 && i != words.size()-1){cout << " ";}}cout << endl;return 0;
}