• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

[Swift]LeetCode692.前K个高频单词|TopKFrequentWords

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号:山青咏芝(shanqingyongzhi)
➤博客园地址:山青咏芝(https://www.cnblogs.com/strengthen/
➤GitHub地址:https://github.com/strengthen/LeetCode
➤原文地址: https://www.cnblogs.com/strengthen/p/10502182.html 
➤如果链接不是山青咏芝的博客园地址,则可能是爬取作者的文章。
➤原文已修改更新!强烈建议点击原文地址阅读!支持作者!支持原创!
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎,请直接点击!!!

进入博主App Store主页,下载使用各个作品!!!

注:博主将坚持每月上线一个新app!!!

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.

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

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

示例 1:

输入: ["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. 假定 k 总为有效值, 1 ≤ k ≤ 集合元素数。
  2. 输入的单词均由小写字母组成。 

扩展练习:

  1. 尝试以 O(n log k) 时间复杂度和 O(n) 空间复杂度解决。

76ms

 1 class Solution {
 2     func topKFrequent(_ words: [String], _ k: Int) -> [String] {
 3         var frequencyList = [String:Int]()
 4         for word in words {
 5             if let count = frequencyList[word] {
 6                 frequencyList[word] = count + 1
 7             } else {
 8                 frequencyList[word] = 1
 9             }
10         }
11         let b = frequencyList.sorted { (dic1, dic2) -> Bool in
12             if dic1.value != dic2.value {
13                 return dic1.value > dic2.value
14             } else {
15                 return dic1.key < dic2.key
16             }
17         }
18         var result = [String]()
19         for item in b {
20             result.append(item.key)
21             if result.count == k {
22                 return result
23             }
24         }
25         return result
26     }
27 }

Runtime: 88 ms
Memory Usage: 20.4 MB
 1 class Solution {
 2     func topKFrequent(_ words: [String], _ k: Int) -> [String] {
 3         var k = k
 4         var res:[String] = [String]()
 5         var freq:[String:Int] = [String:Int]()
 6         var v:[Set<String>] = [Set<String>](repeating:Set<String>(),count:words.count + 1)
 7         for word in words
 8         {
 9             freq[word,default:0] += 1
10         }
11         for (key,val) in freq
12         {
13             v[val].insert(key)
14         }
15         for i in stride(from:v.count - 1,through:0,by:-1)
16         {
17             if k <= 0 {break}
18             var t:[String] = v[i].sorted()
19             if k >= t.count
20             {               
21                 res += t
22             }
23             else
24             {
25 
26                  res += t[0..<k]
27             }
28             k -= t.count
29         }
30         return res
31     }
32 }

88ms

 1 class Solution {
 2     func topKFrequent(_ words: [String], _ k: Int) -> [String] {
 3         var countMap = [String: Int]()
 4         var firstAppearance = [String: Int]()
 5         for (i, word) in words.enumerated() {
 6             countMap[word, default: 0] += 1 
 7             if firstAppearance[word] == nil {
 8                 firstAppearance[word] = i
 9             }
10         }
11         var sortedStringsBasedOnCount = countMap.sorted {
12             return $0.value > $1.value || 
13             ($0.value == $1.value && $0.key < $1.key)
14         }
15         return sortedStringsBasedOnCount[0..<k].map { $0.0 }
16     }
17 }

92ms

 1 class Solution {
 2     func topKFrequent(_ words: [String], _ k: Int) -> [String] {
 3         var countMap = [String: Int]()
 4         words.forEach { countMap[$0, default: 0] += 1 }
 5         var sortedStringsBasedOnCount = countMap.sorted {
 6             return $0.value > $1.value || 
 7             ($0.value == $1.value && $0.key < $1.key)
 8         }
 9         return sortedStringsBasedOnCount[0..<k].map { $0.0 }
10     }
11 }

96ms

 1 class Solution {
 2     func topKFrequent(_ words: [String], _ k: Int) -> [String] {
 3         var wordDict = [String : Int]()
 4         for word in words {
 5             wordDict[word] = 1 + (wordDict[word] ?? 0)
 6         }
 7         return wordDict.sorted { 
 8             $0.value > $1.value || $0.value == $1.value && $0.key < $1.key
 9         }[0..<k].map{$0.key}
10     }
11 }

100ms

 1 class Solution {
 2     func topKFrequent(_ words: [String], _ k: Int) -> [String] {
 3         var frequencyList = [String:Int]()
 4         for word in words {
 5             if let count = frequencyList[word] {
 6                 frequencyList[word] = count + 1
 7             } else {
 8                 frequencyList[word] = 1
 9             }
10         }
11         var frequencyList2 = [[String]](repeating:[String](), count:words.count)
12         for (key, value) in frequencyList {
13             frequencyList2[value].append(key)
14             frequencyList2[value] = frequencyList2[value].sorted()
15         }
16         frequencyList2 = frequencyList2.filter{$0 != [String]()}
17         var result = [String]()
18         var index = frequencyList2.count - 1
19         while index >= 0 {
20             for item in frequencyList2[index] {
21                 result.append(item)
22                 if result.count == k {
23                     return result
24                 }
25             }
26             index -= 1
27         }
28         return result
29     }
30 }

128ms

 1 class Solution {
 2        func topKFrequent(_ words: [String], _ k: Int) -> [String] {
 3         guard words.count > 0 else {
 4             return [String]()
 5         }
 6         
 7         var memo = [String:Int]()
 8         
 9         for w in words {
10             memo[w] = memo[w, default:0] + 1
11         }
12         
13         var helpArray = [[String]]()
14         
15         for key in memo.keys {
16             if let count = memo[key] {
17                 helpArray.append([String(count), key])
18             }
19         }
20         
21         helpArray.sort(by:{
22             if Int($0[0])! > Int($1[0])! {
23                 return true
24             } else if Int($0[0])! < Int($1[0])! {
25                 return false
26             } else {
27                 return $0[1] < $1[1]
28             }
29         })        
30         var sortedArray = helpArray.map{ $0[1] }
31         
32         return Array(sortedArray[0...k - 1])
33     }
34 }

 

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
Swift实现单例模式Singletonpattern的三种方法发布时间:2022-07-13
下一篇:
RealmSwift发布时间:2022-07-13
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap