OD 算法题 B卷【查找舆情热词】

查找舆情热词

• 将每篇文章处理为两个字符串，一个标题，一个正文串；
• 对所有新闻中出现的词语进行处理，输出出现频率最高的topN个词语作为热词；
• 标题中的词语频率系数为3，正文中词语的频率系数为1，结果按照词语频率从高到低排序，当词语出现频率相同时，在标题中出现的频率次数高的排在前面；若仍相同，则按照词语在标题中的先后顺序排序，如果仍相同，则按照词语在正文中为先后顺序排序；

输入描述：
第一行输入正整数N和文章数M;
后续的2M行，每两行为一篇文章的标题串、正文串；
参数限制如下：
0<N<1000, 0<M<100000, 0<每篇文章的词语数<5000

输出描述：
输出出现频率最高的topN个词语，以空格分隔

示例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

输出：
xinguan xinzeng bendi

python实现

• 简单的词语统计；
• 每个词语包含信息 [词语，[总词频次，标题中词频次，标题顺序，正文顺序]]
• 正文中的词语在标题中的词频不累加；
• 标题顺序、正文顺序基于索引表示，且所有标题共用一套索引，所有正文共用一套索引；
• 总词频降序，标题词频降序，标题顺序升序，正文顺序升序；
• 取topN

n, m = list(map(int, input().strip().split()))# key为单词，value为数组
# 数组的信息: 单词出现总次数 标题中出现次数 标题中的顺序 正文中的顺序
word_freq = {}
title_order = 0
text_order = 0
for i in range(m):  # 输出m篇文章# 统计标题词频title = input().strip().split()for j in range(len(title)):if title[j] not in word_freq:# 初始化word_freq[title[j]] = [0, 0, title_order, -1]  # 标题中的索引位置# 更新当前单词的信息info = word_freq[title[j]]# 若单词是首先出现在正文中if info[2] == -1:info[2] = title_order# 标题中出现的词语频率系数为3，正文中出现的词语频率系数为1info[0] += 1*3info[1] += 1   # 标题中1 就是1title_order += 1  # 写一个标题位置，索引+1# 其次是正文text = input().strip().split()for j in range(len(text)):if text[j] not in word_freq:word_freq[text[j]] = [0, 0, -1, text_order]info = word_freq[text[j]]if info[3] == -1:info[3] = text_orderinfo[0] += 1  # 总频次 + 1# 正文中的单词在标题中的频次为0text_order += 1# 组织数组
word_list = []
for word in word_freq:word_list.append([word, word_freq[word]])
# 排序   总频率降序，
word_list = sorted(word_list, key=lambda x: (-x[1][0], -x[1][1], x[1][2], x[1][3]))# 输出
output_str = ""
for i in range(n):output_str += str(word_list[i][0]) + " "print(output_str[:-1])