692. Top K Frequent Words

LeetCode 692. Top K Frequent Words

Description

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:

1. You may assume k is always valid, 1 ≤ k ≤ number of unique elements.

2. Input words contain only lowercase letters.

Follow up:

1. Try to solve it in O ( n log k ) time and O ( n ) extra space.

Tags

Hash Table, Heap, Trie

Solution

For other solutions see Reference section.

The first step is build a hash table who maps a word to its frequency. Then we invert this mapping with a 2D string slice, called freq2word. Its index is word frequency, and the element corresponding to each index in freq2word is an alphabetical-ordered string array, whose elements share the same frequency index. To keep each element of freq2word is sorted, we apply a binary search function to insert each incoming element instead of appending.

After building freq2word, we iterate over it from right. If the length of the current element, which is a slice, is smaller than the result array's remaining capacity, we append all of them to the result. Otherwise, we append words of the current element to the result one by one until the length of the result array is k.

Complexity

• Time complexity: $O(\max(n,m\log(k)))$, m is the number of unique words;

• Space complexity: $O(n)$, actually freq2word stores n words.

Code

func topKFrequent(words []string, k int) []string {
	ans, word2freq, freq2word := make([]string, 0, k), map[string]int{}, make([][]string, len(words))
	for _, word := range words {
		word2freq[word]++
	}
	for w, f := range word2freq {
		if idx := sort.SearchStrings(freq2word[f], w); idx == len(freq2word[f]) {
			freq2word[f] = append(freq2word[f], w)
		} else {
			freq2word[f] = append(freq2word[f][:idx+1], freq2word[f][idx:]...)
			freq2word[f][idx] = w
		}
	}
	for i := len(freq2word) - 1; i >= 0 && len(ans) < k; i-- {
		if k-len(ans) > len(freq2word[i]) {
			ans = append(ans, freq2word[i]...)
			continue
		}
		for j := 0; len(ans) < k; j++ {
			ans = append(ans, freq2word[i][j])
		}
	}
	return ans
}

Reference

1. 前K个高频单词