给一非空的单词列表，返回前k个出现次数最多的单词林大oj

题目描述

给一非空的单词列表，返回前k个出现次数最多的单词。

返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率，按字母顺序排序。

示例

输入: ["i", "love", "leetcode", "i", "love", "coding"], k = 2
输出: ["i", "love"]
解析: "i" 和 "love" 为出现次数最多的两个单词，均为2次。
注意，按字母顺序 "i" 在 "love" 之前。

说明

假定k总为有效值，1 ≤ k ≤ 集合元素数。
输入的单词均由小写字母组成。

解题思路

首先要统计每个单词出现的次数，可以使用哈希表来完成。然后根据出现次数和字母顺序排序，可以使用优先队列来完成。

具体地，将字符串和其出现次数存储到哈希表中，然后将哈希表中的每个元素都加入到优先队列中，队列中元素按照以下规则排序：

- 如果出现次数不同，根据出现次数排序，出现次数多的在前面。
- 如果出现次数相同，根据字母顺序排序，字母靠前的在前面。

最后取出队列前k个元素的字符串即可。

时间复杂度：O(nlogk)。其中n是输入列表的长度，哈希表和优先队列的插入操作的时间复杂度均为O(logk)，总共需要插入n个元素。

空间复杂度：O(n)。哈希表存储n个单词，优先队列存储k个单词。

参考代码

相关问题

xtu oj 最多的可变换字符串 C语言

XTU Online Judge (oj.xtu.edu.cn) 是中国电子科技大学的一个在线编程平台，主要用于算法竞赛和编程练习。在该平台上，"最多可变换字符串"的问题通常涉及动态规划或者字符串操作。题目可能会让你找到两个字符串之间的最短编辑距离，也就是将一个字符串转换成另一个字符串所需的最少插入、删除和替换次数。

例如，你可以用C语言编写如下代码来解决此类问题：

#include <stdio.h>
#include <string.h>

int min(int a, int b, int c) {
    return (a < b) ? ((a < c) ? a : c) : ((b < c) ? b : c);
}

int main() {
    char str1[100], str2[100];
    scanf("%s %s", str1, str2);

    int len1 = strlen(str1), len2 = strlen(str2), dp[len1 + 1][len2 + 1];

    for (int i = 0; i <= len1; ++i)
        dp[i][0] = i;
    for (int j = 0; j <= len2; ++j)
        dp[0][j] = j;

    for (int i = 1; i <= len1; ++i) {
        for (int j = 1; j <= len2; ++j) {
            if (str1[i - 1];
            else
                dp[i][j] = min(dp[i - 1][j - 1], // 替换
                               dp[i - 1][j],      // 删除
                               dp[i][j - 1]);     // 插入
        }
    }

    printf("最少需要 %d 步操作。\n", dp[len1][len2]);

    return 0;
}

c++单词统计oj怎么写

### 回答1：

你可以使用编程语言，比如Python，来实现单词统计。Python有一些内置的函数，可以用来统计字符串中出现的单词。另外，还可以使用第三方库，比如Natural Language Toolkit（NLTK）来进行单词统计。

### 回答2：
要编写一个统计单词的程序，可以按照以下步骤进行：

1. 首先，读取给定的字符串或文本文件。可以使用输入函数从控制台获取字符串，或使用文件读取函数将文本文件的内容读取到程序中。

2. 将读取的字符串进行预处理，去除标点符号和特殊字符。可以使用正则表达式或字符串替换函数来删除这些字符。

3. 将预处理后的字符串进行分词，将其拆分为单词的列表。可以使用字符串分割函数，根据空格或其他分隔符进行拆分。

4. 创建一个字典或哈希表来存储单词及其出现的次数。遍历分词后的单词列表，将每个单词作为键，初始次数设置为0，然后每次遇到相同的单词，次数加1。

5. 最后，按照单词的出现次数进行排序，并将结果打印出来。可以使用排序函数对字典的键值对进行排序，按照次数或键的字母顺序排序。

这是一个基本的单词统计程序的框架。你可以根据具体的需求进行适当的修改和优化，例如加入停用词过滤、大小写转换等功能。总结来说，单词统计程序的核心是对字符串的预处理和分词，以及使用字典来统计每个单词的出现次数。