[Swift]LeetCode451.根据字符出现频率排序|SortCharactersByFrequency

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

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

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

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

Given a string, sort it in decreasing order based on the frequency of characters.

Example 1:

Input:
"tree"

Output:
"eert"

Explanation:
'e' appears twice while 'r' and 't' both appear once.
So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.

Example 2:

Input:
"cccaaa"

Output:
"cccaaa"

Explanation:
Both 'c' and 'a' appear three times, so "aaaccc" is also a valid answer.
Note that "cacaca" is incorrect, as the same characters must be together.

Example 3:

Input:
"Aabb"

Output:
"bbAa"

Explanation:
"bbaA" is also a valid answer, but "Aabb" is incorrect.
Note that 'A' and 'a' are treated as two different characters.

给定一个字符串，请将字符串里的字符按照出现的频率降序排列。

示例 1:

输入:
"tree"

输出:
"eert"

解释:
'e'出现两次，'r'和't'都只出现一次。
因此'e'必须出现在'r'和't'之前。此外，"eetr"也是一个有效的答案。

示例 2:

输入:
"cccaaa"

输出:
"cccaaa"

解释:
'c'和'a'都出现三次。此外，"aaaccc"也是有效的答案。
注意"cacaca"是不正确的，因为相同的字母必须放在一起。

示例 3:

输入:
"Aabb"

输出:
"bbAa"

解释:
此外，"bbaA"也是一个有效的答案，但"Aabb"是不正确的。
注意'A'和'a'被认为是两种不同的字符。

160ms

 1 class Solution {
 2     func frequencySort(_ s: String) -> String {
 3         let a = Array(s)
 4         var dicts = [Character: Int]()
 5         
 6         for e in a {
 7             if let count = dicts[e] {
 8                 dicts[e] = count + 1
 9             } else {
10                 dicts[e] = 1
11             }
12         }
13         
14         let sortedDicts = dicts.sorted { $0.1 > $1.1 }
15         var res = ""
16         for d in sortedDicts {
17             res += String(repeating: d.key, count: d.value)
18         }
19         return res
20     }
21 }

164ms

 1 class Solution {
 2     func frequencySort(_ s: String) -> String {
 3             var dict = [Character: Int]()
 4     for i in s {
 5         dict[i] = (dict[i] ?? 0 ) + 1
 6     }
 7 
 8     let keys = dict.keys.sorted(by: { dict[$0]! >= dict[$1]! } )
 9     var s = ""
10     for key in keys {
11         for _ in 0..<dict[key]! {
12             s.append(key)
13         }
14     }
15     return s
16     }
17 }

184ms

 1 class Solution {
 2     func frequencySort(_ s: String) -> String {
 3         var map: [Character: Int] = [:]
 4         s.forEach { (char) in
 5             if let count = map[char] {
 6                 map[char] = count + 1
 7             } else {
 8                 map[char] = 1
 9             }
10         }
11 
12         return map.lazy.sorted(by: { $0.value > $1.value }).reduce("", { $0 + String(Array(repeating: $1.key, count: $1.value)) })
13     }
14 }

204ms

 1 class Solution {
 2     func frequencySort(_ s: String) -> String {
 3         let array = Array(s.characters)
 4         var map : [Character : Int] = [:]
 5         
 6         for i in 0..<array.count {
 7             var n = map[array[i]]
 8             n = (n ?? 0) + 1
 9             map[array[i]] = n
10         }        
11 
12         var counts = Array(map.values)
13         counts.sort()
14         var ret : [Character] = []        
15         for i in 0..<counts.count {
16             var c : Character = " "
17             let count = counts[counts.count - 1 - i]
18             let keys = Array(map.keys)
19             for key in keys {
20                 let co = map[key]
21                 if co == count {
22                     c = key
23                     break
24                 }
25             }
26             map.removeValue(forKey: c)
27             for j in 0..<count {
28                 ret.append(c)        
29             }
30         }
31         
32         return String(ret)
33     }
34 }

228ms

 1 class Solution {
 2     func frequencySort(_ s: String) -> String {
 3         var dictionary : [Character:Int] = [:]
 4         var answerArray : [Character] = []
 5         for i in s{
 6             if dictionary.keys.contains(i){
 7                 dictionary[i] = dictionary[i]! + 1
 8             } else {
 9                 dictionary[i] = 1
10             }
11         }
12         
13         let sortedKeys = dictionary.sorted{ $0.value > $1.value }
14         
15         for i in sortedKeys{
16             let (key, value) = i
17             for _ in 0..<value{
18                 answerArray.append(key)
19             }
20         }
21         
22         return String(answerArray)
23     }
24 }

260ms

 1 class Solution {
 2     func frequencySort(_ s: String) -> String {
 3         var m = [Character:Int]()
 4         for c in s {
 5             if let count = m[c] {
 6                 m[c] = count + 1
 7             } else {
 8                 m[c] = 1
 9             }
10         }
11         
12         let arr = m.sorted { (arg0, arg1) -> Bool in
13             let a0: (Character, Int) = arg1
14             let a1: (Character, Int) = arg0
15             return a0.1 < a1.1
16         }
17         
18         var carr = [Character]()
19         for tuple in arr {
20             for _ in 0 ..< tuple.value {
21                 carr.append(tuple.key)
22             }
23         }
24         
25         return String(carr)
26     }
27 }

268ms

 1 class Solution {
 2     func frequencySort(_ s: String) -> String {
 3         if s.count == 0 {
 4             return s
 5         }
 6         let chars = s.cString(using: .utf8)!
 7     
 8         var dict = Dictionary<CChar,Int>.init()
 9     
10         for c in chars {
11             if c == 0{
12                 continue
13             }
14             dict[c] = (dict[c] ?? 0) + 1
15         }
16         var result = dict.sorted { (d1,d2) -> Bool in
17             d1.value > d2.value
18         }
19         var newStr = [CChar].init()
20     
21         for (c,index) in result {
22             for i in 0 ..< index {
23                 newStr.append(c)
24             }
25         }
26         newStr.append(0)
27 
28         return String.init(utf8String: newStr) ?? ""
29     }
30 }

348ms

 1 class Solution {
 2     func frequencySort(_ s: String) -> String {
 3         var dict: [Character: Int] = [:]
 4         
 5         for char in s {
 6             dict[char] = (dict[char] ?? 0) + 1
 7         }
 8         
 9         let keys = dict.sorted { $0.value > $1.value}.map { $0.key }
10         
11         var res = ""
12         
13         for char in keys {
14             while dict[char] != 0 {
15                 res += String(char)
16                 dict[char]! -= 1
17             }
18         }
19         
20         return res
21     }
22 }

3388ms

 1 class Solution {
 2     var m:[Character:Int] = [Character:Int]()
 3     func frequencySort(_ s: String) -> String {      
 4         var arr:[Character] = [Character]()
 5         for char in s.characters
 6         {
 7             if m[char] == nil
 8             {
 9                 m[char] = 1
10             }
11             else
12             {
13                 m[char]! += 1
14             }            
15             arr.append(char)
16         }
17         arr.sort(by: sortArray)
18         return String(arr)
19     }
20     
21     func sortArray(_ a:Character,_ b:Character) -> Bool 
22     {
23         return m[a]! > m[b]! || (m[a]! == m[b]! && a < b)
24     }
25 }