【Day 88 】2024-07-04 - 451 根据字符出现频率排序

[azl397985856]

451 根据字符出现频率排序

入选理由

暂无

题目地址

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

前置知识

• 排序算法
• 堆
• 哈希表

  题目描述

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

示例 1:

输入: "tree"

输出: "eert"

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

输入: "cccaaa"

输出: "cccaaa"

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

输入: "Aabb"

输出: "bbAa"

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

[Martina001]

class Solution { public String frequencySort(String s) { Map<Character, Integer> map = new HashMap<Character, Integer>(); int length = s.length(); for (int i = 0; i < length; i++) { char c = s.charAt(i); int frequency = map.getOrDefault(c, 0) + 1; map.put(c, frequency); } List list = new ArrayList(map.keySet()); Collections.sort(list, (a, b) -> map.get(b) - map.get(a)); StringBuffer sb = new StringBuffer(); int size = list.size(); for (int i = 0; i < size; i++) { char c = list.get(i); int frequency = map.get(c); for (int j = 0; j < frequency; j++) { sb.append(c); } } return sb.toString(); } }

[luzhaofeng]

class Solution:
    def frequencySort(self, s: str) -> str:
        count = {}
        for c in s:
            count[c] = count.get(c, 0) + 1
        items = [(-val, key) for key, val in count.items()]
        res = ""
        for val, key in sorted(items):
            res += key * (-val)
        return res

[Dtjk]

class Solution { public: string frequencySort(string s) { unordered_map<char, int> map; for (auto &c : s) map[c]++; vector<pair<char, int>> vec; for (auto &t : map) { vec.push_back(t); } sort(vec.begin(), vec.end(), [](const pair<char, int> &a, const pair<char, int> &b) { return a.second > b.second; }); string ans; for (auto &p : vec) { while (p.second--) ans.push_back(p.first); } return ans; } };

[zhiyuanpeng]

def frequencySort(self, s: str) -> str:
    if not s: return s

    # Convert s to a list.
    s = list(s)

    # Sort the characters in s.
    s.sort()

    # Make a list of strings, one for each unique char.
    all_strings = []
    cur_sb = [s[0]]
    for c in s[1:]:
        # If the last character on string builder is different...
        if cur_sb[-1] != c:
            all_strings.append("".join(cur_sb))
            cur_sb = []
        cur_sb.append(c)
    all_strings.append("".join(cur_sb))

    # Sort the strings by length from *longest* to shortest.
    all_strings.sort(key=lambda string : len(string), reverse=True)

    # Convert to a single string to return.
    # Converting a list of strings to a string is often done
    # using this rather strange looking python idiom.
    return "".join(all_strings)