【Day 88 】2021-12-06 - 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'被认为是两种不同的字符。

[yanglr]

思路:

基于哈希表 + sort来做

代码:

实现语言: C++

class Solution {
public:
    string frequencySort(string s) {
        unordered_map<char, int> dict;
        for (auto& ch : s)
        {
            if (dict.find(ch) == dict.end())
                dict[ch] = 1;
            else dict[ch]++;
        }
        string res;
        vector<pair<char, int>> kvVect;
        for (auto& kvp : dict)
            kvVect.push_back(kvp);        
        auto cmp = [](const pair<char, int>& p1, const pair<char, int>& p2)
        {
            return p1.second > p2.second;
        };
        sort(kvVect.begin(), kvVect.end(), cmp);
        for (auto& kvp : kvVect)
        {
            while (kvp.second--)
                res.push_back(kvp.first);
        } 
        return res;
    }
};

复杂度分析:

• 时间复杂度: O(N logN)
• 空间复杂度: O(N)

[muimi]

代码

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

[ysy0707]

思路：堆+哈希表

class Solution {
    public String frequencySort(String s) {
        //利用大顶堆来排序，哈希表记录字符出现的次数
        HashMap<Character,Integer> map = new HashMap<>();
        PriorityQueue<Character> queue = new PriorityQueue<Character>((a, b) -> map.get(b) - map.get(a));

        //哈希表记录各个字符出现频次
        for(int i = 0; i < s.length(); i++){
            map.put(s.charAt(i), map.getOrDefault(s.charAt(i), 0) + 1);
        }

        //入堆
        for(char c: map.keySet()){
            queue.offer(c);
        }

        //存放结果
        StringBuilder sb = new StringBuilder();
        //取出堆中元素，已经排好大小
        while(!queue.isEmpty()){
            char c = queue.poll();
            int count = map.get(c);

            for(int i = 0; i < count; i++){
                sb.append(c);
            }

        }
        return sb.toString();
    }
}

时间复杂度: O(NlogN) 空间复杂度: O(N)

[thinkfurther]

class Solution:
    def frequencySort(self, s: str) -> str:
        fre = collections.Counter(s)

        fre_list = sorted(fre.items(), key = lambda x: x[1], reverse = True)

        result = ""

        for k, v in fre_list:
            result += k * v

        return result

[chenming-cao]

解题思路

堆+哈希表。建立哈希表储存字符和字符出现的频率。建立大顶堆，将哈希表中的字符放入堆中，然后每次从堆中取出当前出现频率最高的字符，加入到StringBuilder。最后返回字符串即可。

代码

class Solution {
    public String frequencySort(String s) {
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        PriorityQueue<Character> heap = new PriorityQueue<>((a, b) -> map.get(b) - map.get(a));
        for (char key : map.keySet()) {
            heap.offer(key);
        }
        StringBuilder sb = new StringBuilder();
        while (!heap.isEmpty()) {
            char cur = heap.poll();
            int count = map.get(cur);
            while (count > 0) {
                sb.append(cur);
                count--;
            }
        }       
        return sb.toString();
    }
}

复杂度分析

• 时间复杂度：O(n + klogk)，n为字符串s的长度，k为s中不同字符的个数
• 空间复杂度：O(k)

[zhangzz2015]

• 比较直接，先建立hash table，得到每个字符的频率，后对频率进行排序后输出。使用multimap进行排序，也可使用最大堆进行排序。时间复杂度为O(n)，后面的排序操作因为字符个数只有52，基本为O(1)，空间复杂度为hash table的大小，因为自由只有52，也为O(1)。

关键点

代码

• 语言支持：C++

C++ Code:

class Solution {
public:
    string frequencySort(string s) {

        unordered_map<char, int> record; 
        for(int i=0; i< s.size(); i++)
        {
            record[s[i]]++; 
        }
        multimap<int, char, greater<int>> sortNum; 
        for(auto it = record.begin(); it!=record.end(); it++)
        {
            sortNum.insert(make_pair((*it).second, (*it).first));
        }
        string ret; 
        for(auto it = sortNum.begin(); it!= sortNum.end(); it++)
        {
            for(int i=0; i< (*it).first; i++)
                ret.push_back((*it).second); 
        }

        return ret; 

    }
};

[ZacheryCao]

Idea

Heap + Hash table. The hash table is used to record the frequency of the char in the string. The heap is used to sort the char based on its frequency. Each node in the heap will be a tuple containing with two elements: the negative value of the char's frequency and char. The build the answer based on the heap.

Code:

class Solution:
    def frequencySort(self, s: str) -> str:
        count = collections.Counter(s)
        heap = []
        for i in count:
            heapq.heappush(heap, (-count[i], i))
        ans = ""
        while heap:
            i, c = heapq.heappop(heap)
            ans += abs(i) *c
        return ans

Complexity:

Time: O(N + k log k) N: length of the string. K: amount of the unique chars. Space: O(k). Hash table is O(k). Heap is O(k)

[yingliucreates]

link:

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

代码 Javascript

const frequencySort = function (s) {
  let seen = {};
  for (let char of s) {
    seen[char] ? seen[char]++ : (seen[char] = 1);
  }

  let SortedCharactersArray = Object.keys(seen).sort(
    (a, b) => seen[b] - seen[a]
  );

  let result = '';

  for (let char of SortedCharactersArray) result += char.repeat(seen[char]);

  return result;
};

[pophy]

思路

• 桶排序
• 先用map <char, count> 统计每个单词出现次数
• 建立大小为n的bucket，遍历map中的count， 如果count != 0，则bucket[n]加入char
• 最后逆序遍历bucket 如果bucket[i] ！= null 收集答案

Java Code

    public String frequencySort(String s) {
        int n = s.length();
        Map<Character, Integer> countMap = new HashMap();
        for (char c : s.toCharArray()) {
            countMap.put(c, countMap.getOrDefault(c, 0) + 1);
        }
        List<Character>[] buckets = new ArrayList[n + 1];
        for (char c : countMap.keySet()) {
            if (buckets[countMap.get(c)] == null) {
                buckets[countMap.get(c)] = new ArrayList<>();
            }
            buckets[countMap.get(c)].add(c);
        }
        StringBuilder sb = new StringBuilder();
        for (int i = n; i >=0; i--) {
            if (buckets[i] != null) {
                for (char c : buckets[i]) {
                    for (int j = 0; j < i; j++) {
                        sb.append(c);
                    }
                }
            }
        }
        return sb.toString();
    }

时间&空间

• 时间 O(n)
• 空间 O(n)

[wenjialu]

method 1:

thought

hash + sorted

code

class Solution:
    def frequencySort(self, s: str) -> str:
        #hash: key: char; value: times
        # sorted by value. return key 
        hash = {}

        for char in s:
           hash[char] = hash.get(char, 0) + 1
        # print(hash)   
        sorted_hash = sorted(hash.items(), key = lambda x: x[1], reverse = True) 
        print(sorted_hash)
        res = ""  
        for char, freq in sorted_hash:
            # for _ in range(freq):
            #     res += char
            res += char * freq
        return res         

complexity

Time: O(N+KlogK) N: length of s, K: num of diff chars in s (== num of keys in hash); logK??
space: O(N + K)


method2

thought

Bucket sorting

complexity

Time: O(N+ K) N: length of s, K: num of diff chars in s (== num of keys in hash) space: O(N + K)

[biancaone]

class Solution:
    def frequencySort(self, s: str) -> str:
        counter = {}
        res = ''

        for char in s:
            counter[char] = counter.get(char, 0) + 1

        for char, count in sorted(counter.items(), key = lambda x: -x[1]):
            res += char * count

        return res

[skinnyh]

Note

• Count each char's frequency and sort chars based on the frequency.

Solution

class Solution:
    def frequencySort(self, s: str) -> str:
        d = {}
        for c in s:
            d[c] = d.get(c, 0) + 1
        tmp = sorted(d.items(), key=lambda x: x[1], reverse=True)
        res = ''
        for k, v in tmp:
            res += k * v
        return res

Time complexity: O(NlogN)

Space complexity: O(N)

[yuxiangdev]

Naive Approach

public String frequencySort(String s) {
        Map<Character, Integer> map = new HashMap<>();
        for (char c : s.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }

        List<Character> letterOrder = new ArrayList<>(map.keySet());
        Collections.sort(letterOrder, (a, b) -> (map.get(b) - map.get(a)));

        StringBuilder sb = new StringBuilder();
        for (char c : letterOrder) {
            int frequency = map.get(c);
            for (int i = 0; i < frequency; i++) {
                sb.append(c);
            }
        }

        String res = sb.toString();
        return res;
    }

[yan0327]

func frequencySort(s string) string {
    hash := map[byte]int{}
    for i:= range s{
        hash[s[i]]++
    }
    type pair struct{
        ch byte
        count int
    }
    pairs := make([]pair,len(hash))
    for k,v := range hash{
        pairs = append(pairs,pair{k,v})
    }
    sort.Slice(pairs,func(i,j int)bool{
        return pairs[i].count > pairs[j].count
    })
    out := ""
    for _,x := range pairs{
        out += strings.Repeat(string(x.ch),x.count)
    }
    return out
}

[Daniel-Zheng]

思路

哈希表。

代码(C++)

class Solution {
public:
    string frequencySort(string s) {
        unordered_map<char, int> mp;
        int length = s.length();
        for (auto &ch : s) mp[ch]++;
        vector<pair<char, int>> vec;
        for (auto &it : mp) vec.emplace_back(it);
        sort(vec.begin(), vec.end(), [](const pair<char, int> &a, const pair<char, int> &b) {
            return a.second > b.second;
        });
        string ret;
        for (auto &[ch, num] : vec) for (int i = 0; i < num; i++) ret.push_back(ch);
        return ret;
    }
};

复杂度分析

• 时间复杂度：O(N + KLogK)
• 空间复杂度：O(N + K)

[kidexp]

thoughts

先计数，然后根据计数逆序排序 最后拼装

code

from collections import defaultdict
class Solution:
    def frequencySort(self, s: str) -> str:
        char_count_dict = defaultdict(int)
        for char in s:
            char_count_dict[char] += 1
        char_freq_sorted_list = sorted(char_count_dict.items(), key=lambda item: item[1], reverse = True)
        result = ''
        for char, freq in char_freq_sorted_list:
            result  += freq * char
        return result

complexity

Time O(nlgn)

Space O(n)

[wangzehan123]

代码

• 语言支持：Java

Java Code:

public class Solution {
    /**
     * @param s: 
     * @return: return a string
     */
    public String frequencySort(String s) {
        Map<Character, Integer> frequency = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            if (!frequency.containsKey(s.charAt(i))) {
                frequency.put(s.charAt(i), 0);
            }
            frequency.put(s.charAt(i), frequency.get(s.charAt(i)) + 1);
        }

        List<Pair> pairs = new LinkedList<Pair>();
        for (char key : frequency.keySet()) {
            pairs.add(new Pair(key, frequency.get(key)));
        }
        Collections.sort(pairs, new Comparator<Pair>() {
            public int compare(Pair a, Pair b) {
                if (a.frequency == b.frequency) {
                    return (int)a.letter - (int)b.letter;
                }
                return b.frequency - a.frequency;
            }
        });

        StringBuffer result = new StringBuffer("");
        for (Pair pair : pairs) {
            for (int i = 0; i < pair.frequency; i++) {
                result.append(pair.letter);
            }
        }

        return result.toString();
    }
}

class Pair {
    char letter;
    int frequency;
    public Pair(char letter, int frequency) {
        this.letter = letter;
        this.frequency = frequency;
    }

}

[naivecoder-irl]

    public String frequencySort(String s) {
        int n = s.length();
        Map<Character, Integer> countMap = new HashMap();
        for (char c : s.toCharArray()) {
            countMap.put(c, countMap.getOrDefault(c, 0) + 1);
        }
        List<Character>[] buckets = new ArrayList[n + 1];
        for (char c : countMap.keySet()) {
            if (buckets[countMap.get(c)] == null) {
                buckets[countMap.get(c)] = new ArrayList<>();
            }
            buckets[countMap.get(c)].add(c);
        }
        StringBuilder sb = new StringBuilder();
        for (int i = n; i >=0; i--) {
            if (buckets[i] != null) {
                for (char c : buckets[i]) {
                    for (int j = 0; j < i; j++) {
                        sb.append(c);
                    }
                }
            }
        }
        return sb.toString();
    }

[joeytor]

思路

使用堆进行排序

先对词频进行统计

然后将所有 (-frequency, character) 加入堆中 (因为想要大顶堆所以取负数)

然后每次从堆中取出堆顶元素赋值 frequency 遍加入 res string 中

from collections import Counter, defaultdict
import heapq
class Solution:
    def frequencySort(self, s: str) -> str:
        count = Counter(s)
        reverse = defaultdict(list)

        h = []

        for k, v in count.items():
            h.append((-v, k))

        heapq.heapify(h)
        res = ''

        while h:
            v, s = heapq.heappop(h)
            res += (-v)*s

        return res

复杂度

时间复杂度: O(nlogn) 堆的时间复杂度为 O(nlogn) 遍历统计的时间复杂度为 O(n)

空间复杂度: O(n) 堆的空间复杂度

[doveshnnqkl]

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<Character> list = new ArrayList<Character>(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();
    }
}

[ghost]

题目

451. Sort Characters By Frequency

代码

class Solution:
    def frequencySort(self, s: str) -> str:
        d = collections.defaultdict(int)
        hq = []
        res = ''

        for char in s:
            d[char]-=1

        for k,v in d.items():
            heapq.heappush(hq, (v, k))

        while(hq):
            item = heapq.heappop(hq)
            res +=  -item[0] * item[1]

        return res

复杂度

Space: O(n) Time: O(n + klogk)

[chun1hao]

var frequencySort = function (s) {
  let map = new Map();
  for (let i of s) {
    let num = map.get(i) || 0;
    map.set(i, ++num);
  }
  let res = "";
  let arr = Array.from(map).sort((a, b) => b[1] - a[1]);
  for (let [key, val] of arr) {
    res += key.repeat(val);
  }
  return res;
};

[shawncvv]

思路

链表

代码

Python3 Code

class Solution:
    def frequencySort(self, s: str) -> str:

        dict = {}
        for ch in s:
            dict[ch] = dict.get(ch, 0) + 1

        vals = sorted(dict.items(), key=lambda x : x[1], reverse=True)

        res = ""

        for k, v in vals:
            res += k * v

        return res

复杂度

设N为字符个数，K为去重字符个数

• 时间复杂度：O(N+KlogK)
• 空间复杂度：O(K)

[zszs97]

开始刷题

题目简介

【Day 88 】2021-12-06 - 451 根据字符出现频率排序

题目思路

• 按照出现频率排序

题目代码

代码块

class Solution {
public:
    string frequencySort(string s) {
        unordered_map<char, int> mp;
        int length = s.length();
        for (auto &ch : s) {
            mp[ch]++;
        }
        vector<pair<char, int>> vec;
        for (auto &it : mp) {
            vec.emplace_back(it);
        }
        sort(vec.begin(), vec.end(), [](const pair<char, int> &a, const pair<char, int> &b) {
            return a.second > b.second;
        });
        string ret;
        for (auto &[ch, num] : vec) {
            for (int i = 0; i < num; i++) {
                ret.push_back(ch);
            }
        }
        return ret;
    }
};

复杂度

• 空间复杂度 O(n+klogk)
• 时间复杂度 O(n+k)

[okbug]

思路

使用哈希表存，然后使用排序再拼接字符串

var frequencySort = function(s) {
    const map = new Map();

    for (let i = 0; i < s.length; i++) {
        let c = s[i];
        map.set(c, (map.get(c) || 0) + 1);
    }

    return Array.from(map)
        .sort((a, b) => b[1] - a[1])
        .map(item => item[0].repeat(item[1]))
        .join('')
};

[EggEggLiu]

思路

先遍历字符串获取词频哈希表，再将哈希表存到vector中来实现按value排序，最后拼接返回结果字符串

代码

class Solution {
public:
    string frequencySort(string s) {
        unordered_map<char, int> mp;
        int length = s.length();
        for (auto &ch : s) {
            mp[ch]++;
        }
        vector<pair<char, int>> vec;
        for (auto &it : mp) {
            vec.emplace_back(it);
        }
        sort(vec.begin(), vec.end(), [](const pair<char, int> &a, const pair<char, int> &b) {
            return a.second > b.second;
        });
        string ret;
        for (auto &[ch, num] : vec) {
            for (int i = 0; i < num; i++) {
                ret.push_back(ch);
            }
        }
        return ret;
    }
};

复杂度

O(n + klogk)

[user1689]

题目

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

思路

Heap

python3

class Solution:
    def frequencySort(self, s: str) -> str:
        dic = defaultdict(int)
        for char in s:
            dic[char] += 1
        heap = []
        for key, value in dic.items():
            heapq.heappush(heap, (-value, key))
        ans = []
        while(heap):
            freq, char = heapq.heappop(heap)
            ans.append(-freq*char)
        return ''.join(ans)

复杂度分析

• time nlogn
• space n

相关题目

1. 待补充

[ZJP1483469269]

class Solution {
    public String frequencySort(String s) {
        int[][] count = new int[128][2];
        for(int i = 0; i < s.length(); i++){
            int c = (int)(s.charAt(i));
            count[c][0] = c;
            count[c][1]++;
        }
        Arrays.sort(count,(a,b)->{return b[1]-a[1];});
        StringBuilder res = new StringBuilder();
        for(int i = 0 , j = 0; i < s.length(); ){
            int n = count[j][1];
            while(n>0){
                res.append((char)(count[j][0]));
                n--;
                i++;
            }
            j++;
        }
        return res.toString();
    }
}

[jaysonss]

思路

首先使用哈希表计算每个字符出现的次数，然后按照次数作为排序规则建立一个字符的大顶堆

class Solution {
    public String frequencySort(String s) {
        Map<Character,Integer> cmap = new HashMap<>();
        for(int i=0;i<s.length();i++){
            char c = s.charAt(i);
            cmap.put(c,cmap.getOrDefault(c,0)+1);
        }
        Set<Map.Entry<Character,Integer>> set =  cmap.entrySet();
        PriorityQueue<Character> queue = new PriorityQueue<Character>((a,b)->cmap.get(b)-cmap.get(a));

        for(Character c : cmap.keySet()){
            queue.offer(c);
        }

        StringBuilder sb = new StringBuilder();
        while(!queue.isEmpty()){
            Character c = queue.poll();
            for(int i=0;i<cmap.get(c);i++){
                sb.append(c);
            }
        }
        return sb.toString();   
    }
}

假设字符的种类数为k，字符串长度为n

• 时间复杂度：O(n + klogk)
• 空间复杂度：O(k)

[JinhMa]

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(); } }

[shamworld]

var frequencySort = function(s) {
    let map = {};
    for(let char of s){
         map[char] = (map[char]||0)+1;
    }
    const list = [...Object.keys(map)];
    list.sort((a, b) => map[b] - map[a]);
    const res = [];
    const len = list.length;
    for (let i = 0; i < len; i++) {
        const temp = list[i];
        const num = map[temp];
        for (let j = 0; j < num; j++) {
            res.push(temp);
        }
    }
    return res.join('');
};

[wenlong201807]

代码块

const frequencySort = (s) => {
  let res = '';
  const map = new Map();

  // 遍历s，统计计数
  for (let char of s) {
    map.set(char, (map.get(char) || 0) + 1);
  }

  // map根据次数排序，返回数组
  const countArr = [...map].sort((a, b) => b[1] - a[1]);

  for (const [char, count] of countArr) {
    // 利用repeat()方法，对char重复count次
    res += char.repeat(count);
  }

  return res;
};

[pan-qin]

Idea:

Use hashmap to calculate each char's frequency. Sort the map entryset by the frequency. construct the final string.

Complexity:

Time: O(N+KLOGK) K is the number of entry. Space: O(K)

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

    }
}

[learning-go123]

思路

• 堆

代码

• 语言支持：Go

Go Code:

type PriorityQueue [][2]int

func (pq *PriorityQueue) Len() int           { return len(*pq) }
func (pq PriorityQueue) Less(i, j int) bool  { return pq[i][0] > pq[j][0] }
func (pq PriorityQueue) Swap(i, j int)       { pq[i], pq[j] = pq[j], pq[i] }
func (pq *PriorityQueue) Push(x interface{}) { *pq = append(*pq, x.([2]int)) }
func (pq *PriorityQueue) Pop() interface{} {
    res := (*pq)[len(*pq)-1]
    *pq = (*pq)[:len(*pq)-1]
    return res
}

func frequencySort(s string) string {
    var m [123]int
    for _, val := range s {
        m[val]++
    }

    pq := make(PriorityQueue, 0)
    heap.Init(&pq)
    for key, count := range m {
        if count > 0 {
            heap.Push(&pq, [2]int{count, key})
        }
    }

    res := ""
    for pq.Len() > 0 {
        item := heap.Pop(&pq).([2]int)
        for i := 0; i < item[0]; i++ {
            res += string(rune(item[1]))
        }
    }

    return res
}

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(nlogn)$
• 空间复杂度：$O(n)$

[erik7777777]

public String frequencySort(String s) {
        StringBuilder res = new StringBuilder();
        Map<Character, Integer> count = new HashMap<>();
        int maxFreq = 0;
        for (char c : s.toCharArray()) {
            count.put(c, count.getOrDefault(c, 0) + 1);
            maxFreq = Math.max(maxFreq, count.get(c));
        }
        List<Character>[] bucket = new List[maxFreq + 1];
        for (int i = 0;i <= maxFreq;i++) bucket[i] = new ArrayList<>();
        for (char c : count.keySet()) {
            bucket[count.get(c)].add(c);
        }
        for (int i = maxFreq;i >= 1;i--) {
            if (bucket[i].size() > 0) {
                for (char c : bucket[i]) {
                    int num = i;
                    while (num > 0) {
                        res.append(c);
                        num--;
                    }
                }
            } 
        }
        return res.toString();
    }

[tongxw]

思路

分桶排序

代码

class Solution {
    public String frequencySort(String s) {
        Map<Character, Integer> freq = new HashMap<>();
        char[] chars = s.toCharArray();
        int n = s.length();
        for (int i=0; i<n; i++) {
            char c = chars[i];
            freq.put(c, freq.getOrDefault(c, 0) + 1);
        }

        // 建桶
        int maxFreq = Collections.max(freq.values());
        List<Character>[] buckets = new List[maxFreq + 1];
        for (int i=0; i<=maxFreq; i++) {
            buckets[i] = new ArrayList<>();
        }

        // 分桶
        for (Character c : freq.keySet()) {
            buckets[freq.get(c)].add(c);
        }

        StringBuilder sb = new StringBuilder();
        for (int i=maxFreq; i>=0; i--) {
            for (Character c : buckets[i]) {
                for (int j=0; j<i; j++) {
                    sb.append(c);
                }
            }
        }

        return sb.toString();
    }
}

TC: O(len(s)) SC: O(max frequency)

[RocJeMaintiendrai]

代码

class Solution {
    public String frequencySort(String s) {
        Map<Character, Integer> map = new HashMap<>();
        StringBuilder sb = new StringBuilder();
        PriorityQueue<Character> queue = new PriorityQueue<>((a, b) -> map.get(b) - map.get(a));
        for(int i = 0; i < s.length(); i++) {
            map.put(s.charAt(i), map.getOrDefault(s.charAt(i), 0) + 1);
        }
        for(char ch : map.keySet()) {
            queue.offer(ch);
        }
        while(!queue.isEmpty()) {
            char ch = queue.poll();
            int count = map.get(ch);
            for(int i = 0; i < count; i++) {
                sb.append(ch);
            }
        }
        return sb.toString();
    }
}

复杂度分析

时间复杂度

O(nlogn)

空间复杂度

O(n)

[shibingchao123]

var frequencySort = function(s) { const map = new Map();

for (let i = 0; i < s.length; i++) {
    let c = s[i];
    map.set(c, (map.get(c) || 0) + 1);
}

return Array.from(map)
    .sort((a, b) => b[1] - a[1])
    .map(item => item[0].repeat(item[1]))
    .join('')

};

[yyangeee]

官解打卡 class Solution: def frequencySort(self, s: str) -> str:

    dict = {}
    for ch in s:
        dict[ch] = dict.get(ch, 0) + 1

    vals = sorted(dict.items(), key=lambda x : x[1], reverse=True)

    res = ""

    for k, v in vals:
        res += k * v

    return res

[chen445]

代码

class Solution:
    def frequencySort(self, s: str) -> str:
        frequencies=defaultdict(int)

        for char in s:
            frequencies[char]+=1

        heap_frequencies=[]
        for key,value in frequencies.items():
            heap_frequencies.append((value,key))
        heapq._heapify_max(heap_frequencies)

        result=''
        while len(heap_frequencies)>0:
            v,k=heapq._heappop_max(heap_frequencies)
            result+=v*k
        return result

复杂度

Time: O(n+klogk)

Space: O(k)

[Moin-Jer]

思路

---

桶排序

代码

---

class Solution {
    public String frequencySort(String s) {
        Map<Character, Integer> map = new HashMap<Character, Integer>();
        int maxFreq = 0;
        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);
            maxFreq = Math.max(maxFreq, frequency);
        }
        StringBuffer[] buckets = new StringBuffer[maxFreq + 1];
        for (int i = 0; i <= maxFreq; i++) {
            buckets[i] = new StringBuffer();
        }
        for (Map.Entry<Character, Integer> entry : map.entrySet()) {
            char c = entry.getKey();
            int frequency = entry.getValue();
            buckets[frequency].append(c);
        }
        StringBuffer sb = new StringBuffer();
        for (int i = maxFreq; i > 0; i--) {
            StringBuffer bucket = buckets[i];
            int size = bucket.length();
            for (int j = 0; j < size; j++) {
                for (int k = 0; k < i; k++) {
                    sb.append(bucket.charAt(j));
                }
            }
        }
        return sb.toString();
    }
}

复杂度分析

---

• 时间复杂度：O(n + k), n 为 s 的长度， k 为 s 中不同字符的个数
• 空间复杂度：O(n + k)

[ziyue08]

/**
 * @param {string} s
 * @return {string}
 */
var frequencySort = function (s) {
    // 用来统计字符次数用
    let map = new Map();
    let res = '';
    for (let k = 0; k < s.length; k++) {
        map.set(s[k], (map.get(s[k]) || 0) + 1)
    }
    // 排序，让字符多的在前面
    let arr = [...map].sort((a, b) => {
        return b[1] - a[1];
    });
    // 字符串重组
    for (let i = 0; i < arr.length; i++) {
        while (arr[i][1] > 0) {
            res += arr[i][0];
            arr[i][1]--;
        }
    }
    return res;
};

[Richard-LYF]

dict = {} for ch in s: dict[ch] = dict.get(ch, 0) + 1

vals = sorted(dict.items(), key=lambda x : x[1], reverse=True)

res = ""

for k, v in vals:
    res += k * v

return res

[liuyangqiQAQ]

class Solution {
    public String frequencySort(String s) {
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        List<Character> list = new ArrayList<>(map.keySet());
        list.sort((o1, o2) -> map.get(o2) - map.get(o1));
        StringBuilder res = new StringBuilder();
        for (Character c : list) {
            int length = map.get(c);
            for (int i = 0; i < length; i++) {
                res.append(c);
            }
        }
        return res.toString();
    }
}

[BpointA]

思路

桶排序

Python3代码

class Solution:
    def frequencySort(self, s: str) -> str:
        d={}
        m=0
        for i in range(len(s)):
            d[s[i]]=d.get(s[i],0)+1
            m=max(d[s[i]],m)
        h={}
        save=[]
        for i in d:
            if d[i] in h:
                h[d[i]].append(i)
            else:
                save.append(d[i])
                h[d[i]]=[i]

        s=[i for i in range(m,0,-1)]
        print(s)
        result=[]
        print(h)
        s1=""
        for i in s:
            temp=""
            if i not in h:
                continue
            for j in h[i]:
                t=j*i
                temp+=t
            s1+=temp
        return s1

[hewenyi666]

题目名称

451. 根据字符出现频率排序

题目链接

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

题目思路

1.建哈希表，将字符串s中的每个字符计数 2.根据哈希表中的值进行降序排序即可 3.直接字符乘以数目

code for Python3

class Solution(object):
    def frequencySort(self, s):
        """
        :type s: str
        :rtype: str
        """
        hashmap = {}
        for ans in s:
            if ans not in hashmap:
                hashmap[ans] = 1
            else:
                hashmap[ans] += 1
        result = sorted(hashmap.items(),key=lambda hashmap:hashmap[1],reverse=True)
        s = ''
        for i in range(len(result)):
            res = result[i][0] * result[i][1]
            s += res
        return s 

复杂度分析

• 时间复杂度: O(N)
• 空间复杂度: O(N)

[ai2095]

451. Sort Characters By Frequency

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

Topics

-HashMap -Bucket Sort

思路

-HashMap -Bucket Sort

代码 Python

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

    # Determine the frequency of each character.
    counts = collections.Counter(s)
    max_freq = max(counts.values())

    # Bucket sort the characters by frequency.
    buckets = [[] for _ in range(max_freq + 1)]
    for c, i in counts.items():
        buckets[i].append(c)

    # Build up the string.
    string_builder = []
    for i in range(len(buckets) - 1, 0, -1):
        for c in buckets[i]:
            string_builder.append(c * i)

    return "".join(string_builder)

复杂度分析

时间复杂度： O(N)
空间复杂度： O(N)

[falconruo]

思路: 哈希 + 排序

复杂度分析:

• 时间复杂度: O(n + klogk), k为字符串不重复字符个数, n为字符串长度
• 空间复杂度: O(k)

• 代码(C++):

  class Solution {
  public:
  string frequencySort(string s) {
      unordered_map<char, int> freq;
  
      for (auto c : s)
          freq[c]++;
  
      vector<pair<char, int>> ch;
  
      for (auto it = freq.begin(); it != freq.end(); ++it)
          ch.push_back({it->first, it->second});
  
      sort(ch.begin(), ch.end(), [](pair<char, int>& a, pair<char, int>& b) {
          return a.second > b.second;
      });
  
      string sort = "";
  
      for (auto c : ch) {
          for (int i = 0; i < c.second; ++i)
              sort.push_back(c.first);
      }
  
      return sort;
  }
  };

[florenzliu]

Explanation

• hashmap + sort

Code

class Solution:
    def frequencySort(self, s: str) -> str:
        counter = collections.Counter(s)
        res = []
        counter_sorted = sorted(counter.items(), key=lambda kv: kv[1], reverse=True)

        for k, v in counter_sorted:
            res.append(k * v)
        return "".join(res)

Complexity

• Time: O(nlogn)
• Space: O(n)

[banjingking]

public String frequencySort(String s) {

    // Count up the occurances.
    Map<Character, Integer> counts = new HashMap<>();
    for (char c : s.toCharArray()) {
        counts.put(c, counts.getOrDefault(c, 0) + 1);
    }

    // Make a list of the keys, sorted by frequency.
    List<Character> characters = new ArrayList<>(counts.keySet());        
    Collections.sort(characters, (a, b) -> counts.get(b) - counts.get(a));

    // Convert the counts into a string with a sb.
    StringBuilder sb = new StringBuilder();
    for (char c : characters) {
        int copies = counts.get(c);
        for (int i = 0; i < copies; i++) {
            sb.append(c);
        }
    }
    return sb.toString();
}