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

[yetfan]

思路 Counter + 排序 + 输出

代码

class Solution:
    def frequencySort(self, s: str) -> str:
        c = Counter(s)
        res = ""
        for char, num in sorted(list(c.items()), key = lambda x:x[1], reverse = True):
            res += char * num
        return res

复杂度 时间 O(nlogn) 空间 O(n)

[feifan-bai]

思路 1.Counter

代码

class Solution:
    def frequencySort(self, s: str) -> str:
        count = Counter(s)
        ans = ''

        for key, value in sorted(count.items(), key = lambda x:x[1], reverse = True):
            ans += key * value
        return ans

复杂度分析

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

[falconruo]

思路:

哈希 + 排序，统计字符出现次数，按照次数递减排序，组合返回字符串

复杂度分析:

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

代码(C++):

class Solution {
public:
    string frequencySort(string s) {
        if (s.empty() || s.size() == 1) return s;

        map<char, int> freq;
        for (auto c : s)
            freq[c]++;

        vector<pair<char, int>> order;

        for (auto& c : freq)
            order.push_back({c.first, c.second});

        sort(order.begin(), order.end(), [](const pair<char, int>& a, const pair<char, int>& b) {
            return a.second > b.second;
        });

        string res = "";

        for (auto pa : order) {
            for (int i = 0; i < pa.second; ++i)
                res += pa.first;
        }

        return res;
    }
};

[moirobinzhang]

Code:

public string FrequencySort(string s) {
    char[] strArray = s.ToCharArray();
    Dictionary<char, int> mapDict = new Dictionary<char, int>();

    foreach(char c in strArray)
    {
        if (!mapDict.ContainsKey(c))
            mapDict.Add(c, 0);

        mapDict[c]++;
    }

    StringBuilder sb = new StringBuilder();        
    foreach(var item in mapDict.OrderByDescending(m => m.Value).ThenBy(m => m.Key))
    {
        for(int i = 0; i < item.Value; i++)
            sb.Append(item.Key);
    }       

    return sb.ToString(); 
}

[ZacheryCao]

Idea

Hashset and heap

Code

class Solution:
    def frequencySort(self, s: str) -> str:
        counts = collections.Counter(s)
        string_builder = []
        while counts:
            letter, freq = counts.most_common(1).pop()
            string_builder.append(letter * freq)
            del counts[letter]
        return "".join(string_builder)

Complexity:

Time: O(N + klogk). The N is length of the string length. k is the number of unique chars. The Counter.most_common(k) uses heapq.nlargest(k) which has complexity of O(n logk) to have a k length heap, and O(k logk) to get sorted first largest k. Since here the k is 1, it can be approximated to O(N) Space: O(N)

[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(n + maxFreq) = O(n) SC: O(n + maxFreq) = O(n)

[yan0327]

type data struct{
    ch byte
    times int
}
func frequencySort(s string) string {
    hash := map[byte]int{}
    for i := range s{
        hash[s[i]]++
    }
    arr := []data{}
    for i,x := range hash{
        arr = append(arr,data{i,x})
    }
    sort.Slice(arr,func(i,j int)bool{
        return arr[i].times > arr[j].times
    })
    var sb strings.Builder
    for _,x := range arr{
        sb.WriteString(strings.Repeat(string(x.ch),x.times))
    }
    return sb.String()
}

[Tesla-1i]

class Solution:
    def frequencySort(self, s: str) -> str:
        count = Counter(s)
        ans = ''

        for key, value in sorted(count.items(), key = lambda x:x[1], reverse = True):
            ans += key * value
        return ans

[1149004121]

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

思路

用哈希表保存次数，再根据次数对字符进行排序

代码

var frequencySort = function(s) {
    let map = new Map();
    for(let char of s){
        map.set(char, (map.get(char) || 0) + 1);
    };
    let alphas = [...map.keys()];
    alphas.sort((a, b) => map.get(b) - map.get(a));
    let temp = [];
    for(let i = 0; i < alphas.length; i++){
        let char = alphas[i];
        let times = map.get(char);
        for(let i = 0; i < times; i++){
            temp.push(char);
        }
    };
    return temp.join("");
};

复杂度分析

• 时间复杂度：O( N*logN ) 。
• 空间复杂度：O(N) 。

[xuhzyy]

class Solution(object):
    def frequencySort(self, s):
        """
        :type s: str
        :rtype: str
        """
        if len(s) < 2:
            return s

        hash_map = collections.defaultdict(int)
        for ch in s:
            hash_map[ch] += 1
        h = []
        for ch in hash_map:
            heapq.heappush(h, (-hash_map[ch], ch))
        ans = ''
        while(len(h)):
            cnt, ch = heapq.heappop(h)
            ans += ch * (-cnt)
        return ans 

[zhangzz2015]

思路

• 利用hash map 来进行统计频率，后把频率放入multimap进行排序，后输出。也可利用桶排序，时间复杂度为O(n logn) 空间复杂度为 O(n)

关键点

代码

• 语言支持：C++

C++ Code:

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

        unordered_map<char, int> record; 
        for(auto & it: s)
             record[it]++; 

        multimap<int, char> sortFreq; 
        for(auto it = record.begin(); it!= record.end(); it++)
        {
            sortFreq.insert(make_pair((*it).second, (*it).first));
        }
        string ret; 
        for(auto it = sortFreq.rbegin(); it!=sortFreq.rend(); it++)
        {
            for(int i=0; i< (*it).first; i++)
            {
                ret.push_back((*it).second); 
            }
        }
        return ret; 

    }
};

[Tao-Mao]

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

[CoreJa]

这题不难，hash存频率，排序再重组字符即可。

• 直接快排
• 手撕堆
• heapq堆

class Solution:
    # naive排序
    def frequencySort1(self, s: str) -> str:
        d = defaultdict(int)
        for ch in s:
            d[ch] += 1
        ans = ""
        for ch, freq in sorted(d.items(), key=lambda x: x[1], reverse=True):
            ans += ch * freq
        return ans

    # 手撕堆
    def frequencySort2(self, s: str) -> str:
        d = defaultdict(int)
        for ch in s:
            d[ch] += 1
        ans = ""

        heap_max = [0]

        for item in d.items():
            heap_max.append(item)
            index = len(heap_max) - 1
            while index > 1:
                root = index // 2
                if item[1] <= heap_max[root][1]:
                    break
                heap_max[index] = heap_max[root]
                index = root
            heap_max[index] = item

        def max_child_index(index):
            if index * 2 + 1 > len(heap_max) - 1:
                return index * 2
            return index * 2 if heap_max[index * 2][1] > heap_max[index * 2 + 1][1] else index * 2 + 1

        while len(heap_max) > 1:
            ans += heap_max[1][0] * heap_max[1][1]
            item = heap_max[1] = heap_max[-1]
            heap_max.pop()
            if len(heap_max) == 1:
                break
            index = 1
            while index * 2 <= len(heap_max) - 1:
                child = max_child_index(index)
                if item[1] >= heap_max[child][1]:
                    break
                heap_max[index] = heap_max[child]
                index = child
            heap_max[index] = item
        return ans

    # heapq堆
    def frequencySort(self, s: str) -> str:
        d = defaultdict(int)
        for ch in s:
            d[ch] += 1
        ans = ""
        heap_max = [(-freq, ch) for ch, freq in d.items()]
        heapq.heapify(heap_max)
        while heap_max:
            freq, ch = heapq.heappop(heap_max)
            ans += ch * (-freq)
        return ans

[haixiaolu]

思路

哈希 + 排序

class Solution:
    def frequencySort(self, s: str) -> str:
        # count up the occurances
        counts = collections.Counter(s)

        # Build up the string builder
        string_builder = []
        for letter, freq in counts.most_common():
            # letter * freq makes freq copies of letters
            # e.g "a" * 4 -> 'aaaa'
            string_builder.append(letter * freq)

        return "".join(string_builder)

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

[biscuit279]

思路：

哈希表排序

class Solution:
    def frequencySort(self, s: str) -> str:
        freq_dict = {}
        for item in s:
            if item in freq_dict:
                freq_dict[item] += 1
            else: 
                freq_dict[item] = 1 

        freq_list = sorted(freq_dict.items(),reverse = True,key = lambda x :x[1])
        ans = ''
        for item in freq_list:
            ans += item[0] * item[1]
        return ans

时间复杂度：O（n+klogk） 空间复杂度：O（k） 其中k为不重复的字母个数

[LannyX]

思路

PQ

代码

class Solution {
    public String frequencySort(String s) {
        Map<Character, Integer> map = new HashMap();
        PriorityQueue<Character> pq = 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 c : map.keySet()){
            pq.offer(c);
        }
        StringBuilder sb = new StringBuilder();

        while(!pq.isEmpty()){
            char c = pq.poll();
            int count = map.get(c);
            for(int i = 0; i < count; i++){
                sb.append(c);
            }
        }
        return sb.toString();
    }
}

[herbertpan]

思路

1. count frequency

2. 排序，输出

   code

   class Solution {
   public String frequencySort(String s) {
       Map<Character, Integer> charToCount = new HashMap<>();
       for (char ch : s.toCharArray()) {
           charToCount.put(ch, charToCount.getOrDefault(ch, 0) + 1);
       }
   
       // sort the entries by frequency
       List<Map.Entry<Character,Integer>> entries = new ArrayList<>(charToCount.entrySet());
       Collections.sort(entries, new Comparator<Map.Entry<Character,Integer>>(){
           public int compare(Map.Entry<Character,Integer> entry1, Map.Entry<Character,Integer> entry2) {
               return entry2.getValue() - entry1.getValue();
           }
       });
   
       // iterate the sorted set and form the answer
       StringBuilder sb = new StringBuilder();
       Iterator<Map.Entry<Character,Integer>> it = entries.iterator();
       while (it.hasNext()) {
           Map.Entry<Character,Integer> entry = it.next();
           for (int i = 0; i < entry.getValue(); i++) {
               sb.append(entry.getKey());
           }
       }   
       return sb.toString();
   }  
   }

   complexity

3. time：O(nlogn) n is the length of input string
4. space: O(n)

[xinhaoyi]

class Solution { //桶排序 public String frequencySort(String s) { char[] chs = s.toCharArray(); Map<Character, Integer> map = new HashMap<>(); int maxTimes = -1; //统计每个字母的频次，并存入哈希表 for(char c : chs){ if(!map.containsKey(c)){ map.put(c, 1); }else{ map.put(c, map.get(c) + 1); } maxTimes = map.get(c) > maxTimes ? map.get(c) : maxTimes; } //新建一个桶，将字母存入索引为它的频次的桶里 ArrayList[] buckets = new ArrayList[maxTimes + 1]; for(char c : map.keySet()){ int frequency = map.get(c); if(buckets[frequency] == null){ buckets[frequency] = new ArrayList<>(); } buckets[frequency].add(c); } //倒着遍历桶，将桶里的字母取出来，并按照它的频次插入字符数组中 int p = 0; for(int i = maxTimes; i >= 0; i--){ if(buckets[i] != null){ for(char c : buckets[i]){ //buckets[i]这个桶里的字母的频次为i，因此要插入i个到结果集中 for(int j = 0; j < i; j++){ //复用chs作为结果集 chs[p++] = c; } } } } return new String(chs); } }

[JudyZhou95]

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

        counter = collections.Counter(s)

        heap = [(-v, k) for (k, v) in counter.items()]
        heapq.heapify(heap)

        res = ""
        while heap:
            neg_v, k = heapq.heappop(heap)
            for i in range(-neg_v):
                res += k

        return res

[callmeerika]

思路

哈希+堆排序

代码

var Heap = function (arr) {
  this.queue = [];
  this.size = 0;
  this.init(arr);
};
Heap.prototype.init = function (arr) {
  this.size = arr.length;
  this.queue = new Array(arr.length + 1);
  let i = 1;
  for (let val of arr) {
    this.queue[i++] = val;
  }
  this.buildHeap();
};
Heap.prototype.buildHeap = function () {
  for (let i = this.size >> 1; i > 0; i--) {
    this.goDown(i);
  }
};
Heap.prototype.goDown = function (i) {
  let temp = this.queue[i];
  while (i << 1 <= this.size) {
    let child = i << 1;
    // child < size 表示当前元素有右节点
    if (
      child < this.size &&
      this.queue[child + 1].value > this.queue[child].value
    ) {
      child++;
    }
    if (temp.value >= this.queue[child].value) break;
    this.queue[i] = this.queue[child];
    i = child;
  }
  this.queue[i] = temp;
};
Heap.prototype.isEmpty = function () {
  return this.size <= 0;
};
Heap.prototype.pop = function () {
  if (this.isEmpty()) {
    return null;
  }
  let res = this.queue[1];
  this.queue[1] = this.queue.pop();
  this.size--;
  this.goDown(1);
  return res;
};

var frequencySort = function (s) {
  let n = s.length;
  let hash = new Map();
  let arr = [];
  for (let vv of s) {
    hash.set(vv, (hash.get(vv) || 0) + 1);
  }
  for (let [key, value] of hash.entries()) {
    arr.push({
      key: key,
      value: value,
    });
  }
  let heap = new Heap(arr);
  let res = "";
  while (!heap.isEmpty()) {
    let { key, value } = heap.pop();
    for (let i = 0; i < value; i++) {
      res += key;
    }
  }
  return res;
};

复杂度

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

[Aobasyp]

思路 统计字符个数，再把个数排个序

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

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

[dahaiyidi]

Problem

[451. 根据字符出现频率排序](https://leetcode-cn.com/problems/sort-characters-by-frequency/)

++

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

示例 1:

输入:
"tree"

输出:
"eert"

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

---

Note

• 桶排序
• 桶排序的本质是，将出现的频率相同的元素聚集在一起。

---

Complexity

• 时间O：n+k， n是字符串长度，k是字符串不同字符的数量
• 空间O：n+k

---

Python

C++

class Solution {
public:
    string frequencySort(string s) {
        string res;
        unordered_map<char, int> mp;
        int max_freq = 0;
        // 统计每个字符的数量
        for(auto& ch: s){
            max_freq = max(max_freq, ++mp[ch]);
        }

        // 根据数量汇集字符
        vector<string> buckets(max_freq + 1);
        for(auto& [ch, count]: mp){
            buckets[count].push_back(ch);
        }

        for(int count = max_freq; count >= 1; count--){
            string temp = buckets[count];
            for(auto& ch: temp){

                // 插入ch字符count次
                for(int i = 0; i < count; i++){
                    res.push_back(ch);
                }
            }
        }
        return res;
    }
};

From : https://github.com/dahaiyidi/awsome-leetcode

[Rex-Zh]

思路

• 哈希表统计每个字符出现的次数
• 按每个字符出现的次数调用库函数进行排序
• 将排序后的字符进行拼接

  代码

  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)，N为字符个数，K为去重字符个数
• 空间：直接排序：O(K)，K为去重字符个数

[ZJP1483469269]

class Solution:
    def frequencySort(self, s: str) -> str:
        cnt = Counter(s)
        p = []
        for c , n in cnt.items():
            heappush(p , (-n , c))
        ans = ''
        while p:
            n , c = heappop(p)
            for _ in range(-n):
                ans += c

        return ans

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

[zzzpppy]

class Solution {
    class Node {
        char c; 
        int v;
        Node(char _c, int _v) {
            c = _c; v = _v;
        }
    }
    public String frequencySort(String s) {
        char[] cs = s.toCharArray();
        Map<Character, Integer> map = new HashMap<>();
        for (char c : cs) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        PriorityQueue<Node> q = new PriorityQueue<>((a,b)->{
            if (b.v != a.v) return b.v - a.v;
            return a.c - b.c;
        });
        for (char c : map.keySet()) {
            q.add(new Node(c, map.get(c)));
        }
        StringBuilder sb = new StringBuilder();
        while (!q.isEmpty()) {
            Node poll = q.poll();
            int k = poll.v;
            while (k-- > 0) sb.append(poll.c);
        }
        return sb.toString();
    }
}

[hdyhdy]

import "container/heap"
func frequencySort(s string) string {
    num := make(map[byte][]byte,0)
    for i := range s {
        num[s[i]] = append(num[s[i]],s[i])
    }
    h := &hp{}
    heap.Init(h)
    for _,value := range num{
        heap.Push(h,value)
    }
    var ans []byte 
    for len(*h) > 0 {
        ans = append(ans,heap.Pop(h).([]byte)...)
    }
    return string(ans)
}

type hp [][]byte

func (h hp)Len() int{
    return len(h)
} 

func (h hp)Swap(i,j int){
    h[i],h[j] = h[j],h[i]
}

func (h hp)Less(i,j int)bool{
    return len(h[i]) > len(h[j])
}

func (h *hp)Push(x interface{}){
    *h = append(*h,x.([]byte))
}

func (h *hp)Pop() interface{}{
    x := *h
    ans := x[len(x)-1]
    *h = x[:len(x)-1]
    return ans 
}

[declan92]

class Solution {

public String frequencySort(String s) {

    Map<Character, Integer> counter = new HashMap<>();

    for (int i = 0; i < s.length(); i++)
        counter.put(s.charAt(i), counter.getOrDefault(s.charAt(i), 0) + 1);

    List<Map.Entry<Character, Integer>> list = new ArrayList<>(counter.entrySet());

    Collections.sort(list, new Comparator<Map.Entry<Character, Integer>>() {

        @Override
        public int compare(Map.Entry<Character, Integer> o1, Map.Entry<Character, Integer> o2) {

            return o2.getValue() - o1.getValue();
        }
    });

    StringBuilder res = new StringBuilder();

    for (Map.Entry<Character, Integer> entry : list)
        for (int i = 0; i < entry.getValue(); i++)
            res.append(entry.getKey());

    return res.toString();
}

} 时间:O(N+KlogK) 空间:O(k)

[Hacker90]

import "container/heap" func frequencySort(s string) string { num := make(map[byte][]byte,0) for i := range s { num[s[i]] = append(num[s[i]],s[i]) } h := &hp{} heap.Init(h) for _,value := range num{ heap.Push(h,value) } var ans []byte for len(*h) > 0 { ans = append(ans,heap.Pop(h).([]byte)...) } return string(ans) }

type hp [][]byte

func (h hp)Len() int{ return len(h) }

func (h hp)Swap(i,j int){ h[i],h[j] = h[j],h[i] }

func (h hp)Less(i,j int)bool{ return len(h[i]) > len(h[j]) }

func (h hp)Push(x interface{}){ h = append(*h,x.([]byte)) }

func (h hp)Pop() interface{}{ x := h ans := x[len(x)-1] *h = x[:len(x)-1] return ans }

[fornobugworld]

class Solution:
    def frequencySort(self, s: str) -> str:
        dic = dict()
        for i  in s:
            if not i in dic:
                dic[i] = 1
            else:
                dic[i] +=1
        dicNew = sorted(dic.items(), key = lambda kv:(kv[1],kv[0]),reverse = True)
        ans  = ""
        for j in dicNew:
            ans += j[0]*j[1]
        return ans

[GaoMinghao]

class Solution {
    class singleRecord {
        char c;
        int count;

        public singleRecord(char c, int count) {
            this.c = c;
            this.count = count;
        }

    }

    public String frequencySort(String s) {
        Map<Character, Integer> records = new HashMap<>();
        for(char c:s.toCharArray()) {
            records.merge(c, 1, (a, b) -> records.get(c) + b);
        }
        PriorityQueue<singleRecord> heap = new PriorityQueue<>(new Comparator<singleRecord>() {
            @Override
            public int compare(singleRecord o1, singleRecord o2) {
                return o2.count - o1.count;
            }
        });
        for(Map.Entry<Character, Integer> single:records.entrySet()) {
           heap.add(new singleRecord(single.getKey(), single.getValue()));
        }
        StringBuilder ans = new StringBuilder();
        while (!heap.isEmpty()) {
            singleRecord singleRecord = heap.poll();
            for(int i = 0; i <singleRecord.count; i++) {
                ans.append(singleRecord.c);
            }
        }
        return ans.toString();
    }
}

[Jay214]

/**
 * @param {string} s
 * @return {string}
 */
var frequencySort = function(s) {
    let map = {}
    s.split('').forEach(str => {
        map[str] = (map[str] || 0) + 1
    })
   map = Object.entries(map)
   map.sort((a, b) => b[1] - a[1])
   return map.map(([key,v]) => new Array(v).fill(key).join('')).join('')
};

[ggohem]

思路：

可以使用桶排序的思想，根据出现次数生成排序后的字符串。

代码：

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)

• 空间：O(n+k)

[machuangmr]

代码

class Solution {

    class Node{
        char c;
        int v;
        Node(char c, int v) {
            this.c = c;
            this.v = v;
        }
    }

    public String frequencySort(String s) {
        if(s.isEmpty()) return "";
        Map<Character, Integer> map = new HashMap<>();
        for(int i = 0;i < s.length();i++) {
            char temp = s.charAt(i);
            map.put(temp, map.getOrDefault(temp, 0) + 1);
        }
        PriorityQueue<Node> queue = new PriorityQueue<>( (a, b) -> {
            if(a.v != b.v) {
                return b.v -a.v;
            }
            return a.c - b.c;
        });
        for(char c : map.keySet()) {
            queue.add(new Node(c, map.get(c)));
        }
        StringBuilder sb = new StringBuilder(); 
        while(!queue.isEmpty()) {
            Node res = queue.poll();
            int value = res.v;
            while(value-- >0) {
                sb.append(res.c);
            }
        }
        return sb.toString();
    }
}

[hx-code]

class Solution {

class Node{
    char c;
    int v;
    Node(char c, int v) {
        this.c = c;
        this.v = v;
    }
}

public String frequencySort(String s) {
    if(s.isEmpty()) return "";
    Map<Character, Integer> map = new HashMap<>();
    for(int i = 0;i < s.length();i++) {
        char temp = s.charAt(i);
        map.put(temp, map.getOrDefault(temp, 0) + 1);
    }
    PriorityQueue<Node> queue = new PriorityQueue<>( (a, b) -> {
        if(a.v != b.v) {
            return b.v -a.v;
        }
        return a.c - b.c;
    });
    for(char c : map.keySet()) {
        queue.add(new Node(c, map.get(c)));
    }
    StringBuilder sb = new StringBuilder(); 
    while(!queue.isEmpty()) {
        Node res = queue.poll();
        int value = res.v;
        while(value-- >0) {
            sb.append(res.c);
        }
    }
    return sb.toString();
}

}

[for123s]

class Solution {
public:
    string frequencySort(string s) {
        unordered_map<char, int> mp;
        int maxFreq = 0;
        int length = s.size();
        for (auto &ch : s) {
            maxFreq = max(maxFreq, ++mp[ch]);
        }
        vector<string> buckets(maxFreq + 1);
        for (auto &[ch, num] : mp) {
            buckets[num].push_back(ch);
        }
        string ret;
        for (int i = maxFreq; i > 0; i--) {
            string &bucket = buckets[i];
            for (auto &ch : bucket) {
                for (int k = 0; k < i; k++) {
                    ret.push_back(ch);
                }
            }
        }
        return ret;
    }
};

[ChenJingjing85]

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

[taojin1992]

class Solution {
    /*
    s.length() = n, unique letters = m
    time: 
    O(n) + O(mlogm) + O(m * (logm + maxfreq))

    space: O(m) + O(n)
    */
    public String frequencySort(String s) {
        Map<Character, Integer> letterFreqMap = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            letterFreqMap.put(s.charAt(i), letterFreqMap.getOrDefault(s.charAt(i), 0) + 1);
        }
        PriorityQueue<Map.Entry<Character, Integer>> maxHeap = new PriorityQueue<>((a, b) -> (b.getValue() - a.getValue()));

        for (Map.Entry<Character, Integer> entry : letterFreqMap.entrySet()) {
            maxHeap.offer(entry);
        }
        StringBuilder sb = new StringBuilder();
        while (!maxHeap.isEmpty()) {

            Map.Entry<Character, Integer> cur = maxHeap.poll();
            int freq = cur.getValue();
            char letter = cur.getKey();
            for (int i = 0; i < freq; i++) {
                sb.append(letter);
            }
        }
        return sb.toString();
    }
}

[Richard-LYF]

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

    d = {}

    for i in s:
        if i not in d:
            d[i] = 1
        else:
            d[i] += 1

    l = sorted(d.items(),key = lambda x:-x[1])
    res = ''
    for j in l:
        res += j[0] *j[1]

    return res