692. Top K Frequent Words

Medium
Given an array of strings words and an integer k, return the k most frequent strings.
Return the answer sorted by the frequency from highest to lowest. Sort the words with the same frequency by their lexicographical order.
Example 1:
Input: words = ["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: words = ["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.
Constraints:
  • 1 <= words.length <= 500
  • 1 <= words[i].length <= 10
  • words[i] consists of lowercase English letters.
  • k is in the range [1, The number of unique words[i]]
Follow-up: Could you solve it in O(n log(k)) time and O(n) extra space?
​

解題

func topKFrequent(words []string, k int) []string {
count := make(map[string]int)
for _, val := range words {
if _,ok := count[val]; ok {
count[val]++
} else {
count[val] = 1
}
}
​
type kv struct {
Key string
Value int
}
​
var ss []kv
for k, v := range count {
ss = append(ss, kv{k, v})
}
​
sort.Slice(ss, func(i, j int) bool {
if ss[i].Value==ss[j].Value {
return ss[i].Key < ss[j].Key
}
return ss[i].Value > ss[j].Value
})
​
ans := []string{}
for i:=0; i<k; i++ {
ans = append(ans, ss[i].Key)
}
return ans
}
也可以不用struct。
func topKFrequent(words []string, k int) []string {
count := make(map[string]int)
for _, val := range words {
if _,ok := count[val]; ok {
count[val]++
} else {
count[val] = 1
}
}
​
keys := make([]string, 0, len(count))
for key := range count {
keys = append(keys, key)
}
sort.Slice(keys, func(i, j int) bool {
if count[keys[i]] == count[keys[j]] {
return keys[i] < keys[j]
}
return count[keys[i]] > count[keys[j]]
})
return keys[:k]
}