- Given a non-empty list of words, return the k most frequent elements.
- Your answer should be sorted by frequency from highest to lowest. If two words have the same frequency, then the Word with the lower alphabetical order comes first.
- Example 1:
- Input: ["i", "love", "leetcode", "i", "love", "coding"], k = 2
- Output: ["i", "love"]
- Explanation: "i" and "love" are the two most frequent words.
- Note that "i" comes before "love" due to a lower alphabetical order.
- Example 2:
- Input: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4
- Output: ["the", "is", "sunny", "day"]
- Explanation: "the", "is", "sunny" and "day" are the four most frequent words,
- with the number of occurrence being 4, 3, 2 and 1 respectively.
- Note:
You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
Input words contain only lowercase letters.
- Follow up:
- Try to solve it in O(n log k) time and O(n) extra space.
- time: O(nlogk), space: O(n)
- class Solution {
- public List<String> topKFrequent(String[] words, int k) {
- Map<String, Integer> map = new HashMap<>();
- for(String Word : words) {
- map.put(Word, map.getOrDefault(Word, 0) + 1);
- }
- PriorityQueue<String> heap = new PriorityQueue<>((a, b) -> map.get(a) == map.get(b) ? b.compareTo(a) : (map.get(a) - map.get(b)));
- for(Map.Entry<String, Integer> entry : map.entrySet()) {
- heap.offer(entry.getKey());
- if(heap.size()> k)
- heap.poll();
- }
- List<String> res = new ArrayList<>();
- while(res.size() < k) {
- res.add(0, heap.poll());
- }
- return res;
- }
- }
来源: http://www.bubuko.com/infodetail-2893002.html