【LeetCode】 前K个高频单词 两种解法

给定一个单词列表 words 和一个整数 k ，返回前 k 个出现次数最多的单词。

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

示例 1：

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

示例 2：

输入: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4
输出: ["the", "is", "sunny", "day"]
解析: "the", "is", "sunny" 和 "day" 是出现次数最多的四个单词，
    出现次数依次为 4, 3, 2 和 1 次。

注意：

• 1 <= words.length <= 500
• 1 <= words[i] <= 10
• words[i] 由小写英文字母组成。
• k 的取值范围是 [1, 不同 words[i] 的数量]

思路：

首先想到了map做键值对映射，记录单词的出现次数，最后造个数组排序就行，但是面试一紧张忘了map怎么用了，只能另辟蹊径，改用C++结构体，分别记录单词，出现次数，是否是第一次出现

结构体解法：

struct ac {
			string word;
			int num;
			int flag;
		} a[505];
 
 
bool cmp(ac a, ac b) {
			if (a.num == b.num) {
				return a.word < b.word;
			}
			return a.num > b.num;
		}
class Solution {
	public:
		
		vector topKFrequent(vector& words, int k) {
			vector res;
			int i, j;
			for (i = 0; i < words.size(); i++) {
//		cout<
				a[i].word = words[i];
				a[i].num = 0;
				a[i].flag = 0;
			}
 
			for (i = 0; i < words.size(); i++) {
				for (j = 0; j < words.size(); j++) {
					if (a[j].word == words[i]) {
 
						if (a[j].num != 0)
							a[j].flag = 1;
						a[j].num++;
 
					}
				}
			}
 
			sort(a, a + words.size(), cmp);
 
			for (i = 0; i < words.size(); i++) {
 
				cout << "--" << a[i].word << " " << a[i].num << endl;
			}
 
			for (i = 0; i < words.size(); i++) {
				if (i != 0 && a[i].word == a[i - 1].word)
					continue;
				res.push_back(a[i].word);
//		cout << a[i].word << endl;
				k--;
				if (k <= 0)
					break;
			}
 
			return res;
		}
};

map解法：

struct ac {
	string word;
	int num;
	int flag;
} a[505];
 
 
bool cmp(ac a, ac b) {
	if (a.num == b.num) {
		return a.word < b.word;
	}
	return a.num > b.num;
}
class Solution {
	public:
 
		vector topKFrequent(vector& words, int k) {
			vector res;
			int i, j;
 
			mapint> mp;
 
			// for (i = 0; i < 6; i++) {
			// 	string s;
			// 	cin >> s;
			// 	words.push_back(s);
			// }
 
			for (i = 0; i < words.size(); i++) {
//		cout<
				mp[words[i]]++;
			}
 
			i = 0;
			mapint>::iterator it;
			for (it = mp.begin(); it != mp.end(); it++) {
				a[i].word = it->first;
				a[i].num = it->second;
				i++;
			}
 
			sort(a, a + i, cmp);
 
//	for (i = 0; i < words.size(); i++) {
//		cout << "--" << a[i].word << " " << a[i].num << endl;
//	}
 
			for (i = 0; i < k; i++) {
				res.push_back(a[i].word);
//		cout<
			}
 
			return res;
		}
};