題目

https://leetcode.com/problems/sort-characters-by-frequency/

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.

解答

C#

public class Solution {
    public string FrequencySort(string s) {
        var map = new Dictionary<char, int>();
        var cs = s.ToCharArray();
        for (int i = 0; i < cs.Length; i++)
        {
            if (map.ContainsKey(cs[i]))
            {
                map[cs[i]] = map[cs[i]] + 1;
            }
            else
            {
                map.Add(cs[i], 1);
            }
        }
        var sort = map.OrderByDescending(x => x.Value);
        StringBuilder result = new StringBuilder();
        foreach (var item in sort)
        {
            for (int i = 0; i < item.Value; i++)
            {
                result = result.Append(item.Key);
            }
        }
        return result.ToString();
    }
}

結果

Runtime: 96 ms, faster than 96.12% of C# online submissions.

Memory Usage: 25.5 MB, less than 100% of C# online submissions.

Time Complexity: O(n^2)

Space Complextiy: O(n)

為什麼我要這樣做？

這題比想像中簡單，其實他就是要照使用者輸入的 string 每個字元的個數大小，排序後回傳。

1. 使用 Dictionary 去計算每個 char 在 string 裡的個數
2. 計算完後，根據個數大小降冪排序
3. 用 for 迴圈將已排序好的 sort (IOrderedEnumerable) 根據每個字元個數透過 StringBuilder 串接
   • 動態串接字串時，使用 StringBuilder 效能比 String 好
4. 回傳時，將 StringBuilder 轉為 string (ToString())

以上就是這次 LeetCode 刷題的分享啦！
如果其它人有更棒的想法及意見，請留言或寄信(t4730@yahoo.com.tw) 給我。
那我們就下回見囉