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

[LIMBO42]

class Solution:
    def frequencySort(self, s: str) -> str:
        dic = collections.defaultdict(int)
        for ch in s:
            dic[ch] = dic[ch] + 1
        m_sorted = sorted(dic.items(), key = lambda x : x[1], reverse=True)
        ans = ''
        for ch, v in m_sorted:
            ans = ans + ch * v
        return ans

[huizsh]

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 ch : map.keySet())
        pq.offer(ch);

    StringBuilder res = new StringBuilder();

    while(!pq.isEmpty()){

        char c = pq.poll();
        int count = map.get(c);

        for (int i = 0; i < count; i++)
            res.append(c);

    }

    return res.toString();
}

}

[Diana21170648]

思路

直接排序

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:#k是字符串，v是出现的次数
            res+=k*v
        return res

**复杂度分析**
- 时间复杂度：O(N+KlogK)，其中 N 为字符串个数，K为去重字符串个数。
- 空间复杂度：O(K)

[csthaha]

/**
 * @param {string} s
 * @return {string}
 */
var frequencySort = function(s) {
    const map = new Map();
    for(let str of s) {
        map.set(
            str,
            (map.get(str) || 0) + 1
        )
    }
    const sortArr = [...map.entries()].sort((a, b) => b[1] - a[1]);
    return sortArr.reduce((pre, next) => pre + next[0].repeat(next[1]), '')
};

[wangqianqian202301]

class Solution:
    def frequencySort(self, s: str) -> str:
        counter = collections.Counter(s)
        items = counter.items()
        sortedItems = sorted(items, key=lambda x: x[1], reverse=True)
        rtn = ""
        for i in sortedItems:
            rtn = rtn + i[0] * i[1]
        return rtn

[Abby-xu]

class Solution: def frequencySort(self, s: str) -> str: c1, c2 = Counter(s), {} for k,v in c1.items(): c2.setdefault(v, []).append(k*v) return "".join(["".join(c2[i]) for i in range(len(s), -1, -1) if i in c2])

[harperz24]

class Solution:
    def frequencySort(self, s: str) -> str:
        freq_counter = collections.Counter(s)
        freqs = [(freq, ch) for ch, freq in freq_counter.items()]

        min_freq = min(freqs)[0]
        max_freq = max(freqs)[0]

        buckets = [[] for _ in range(max_freq - min_freq + 1)]
        for freq in freqs:
            index = max_freq - freq[0]
            buckets[index].append(freq)

        res = ""
        for bucket in buckets:
            if bucket:
                for freq, ch in bucket:
                    res += freq * ch

        return res

    # bucket sort
    # time: O(n + k)
    # space: O(n + k)

[snmyj]

class Solution {
public:
    set<pair<int,char>> ss;
    vector<pair<int,char>> res;
    unordered_map<char,int> smap;
    string ans={};
    string frequencySort(string s) {
         for(auto x:s){

             if(smap.count(x)) {
                 ss.erase({smap[x],x});
                 smap[x]++;
                 ss.insert({smap[x],x});
             }
             else{
                 smap[x]++;
                 ss.insert({smap[x],x});
             }
         }
         for(auto x:ss){
           res.push_back({x.first,x.second});
         }
         for(int i=res.size()-1;i>=0;i--){
             int cnt=res[i].first;
             for(int j=0;j<cnt;j++) ans+=res[i].second;
         }
         return ans;
    }
};

[zhangyu1131]

class Solution {
public:
    string frequencySort(string s) {
        unordered_map<char, int> map;
        for (char& c : s)
        {
            map[c]++;
        }
        vector<pair<char, int>> vec;
        for (auto iter = map.begin(); iter != map.end(); ++iter)
        {
            vec.push_back(make_pair(iter->first, iter->second));
        }
        sort(vec.begin(), vec.end(), [](pair<char, int>& p1, pair<char, int>& p2) {return p1.second > p2.second;});

        string res = "";
        for (auto& pair : vec)
        {
            string tmp(pair.second, pair.first);
            res += tmp;
        }

        return res;
    }
};

[FireHaoSky]

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()]
        heapq.heapify(items)
        res = ""
        while items:
            val, key = heapq.heappop(items)
            res += key * (-val)
        return res

[airwalkers]

class Solution {
    public String frequencySort(String s) {
        int[][] count = new int[128][2];
        for (int i = 0; i < 128; i++) {
            count[i] = new int[] {0, i};
        }
        for (char ch: s.toCharArray()) {
            count[ch][0]++;
        }
        Arrays.sort(count, (o1, o2) -> o2[0] - o1[0]);
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 128; i++) {
            for (int j = 0; j < count[i][0]; j++) {
                sb.append((char)(count[i][1]));
            }
        }
        return sb.toString();
    }
}

[bookyue]

    public String frequencySort(String s) {
        int[] cnt = new int['z' + 1];
        for (int i = 0; i < s.length(); i++) 
            cnt[s.charAt(i)]++;

        var pq = new PriorityQueue<Integer>(Comparator.comparing(i -> -cnt[i]));
        for (int i = 0; i < cnt.length; i++) {
            if (cnt[i] == 0) continue;
            pq.offer(i);
        }

        StringBuilder sb = new StringBuilder();
        while (!pq.isEmpty()) {
            char c = (char) (pq.poll().intValue());
            sb.append(Character.toString(c).repeat(cnt[c]));
        }

        return sb.toString();
    }

[chanceyliu]

代码

function frequencySort(s: string): string {
  const map = new Map();
  const length = s.length;
  for (let i = 0; i < length; i++) {
    const c = s[i];
    const frequency = (map.get(c) || 0) + 1;
    map.set(c, frequency);
  }
  const list = [...map.keys()];
  list.sort((a, b) => map.get(b) - map.get(a));
  const sb = [];
  const size = list.length;
  for (let i = 0; i < size; i++) {
    const c = list[i];
    const frequency = map.get(c);
    for (let j = 0; j < frequency; j++) {
      sb.push(c);
    }
  }
  return sb.join('');
};

[JasonQiu]

class Solution:
    def frequencySort(self, s: str) -> str:
        frequency = Counter(s).most_common()
        result = ""
        for char, freq in frequency:
            result += char * freq
        return result

[Lydia61]

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

思路

桶排序算法

代码

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

[kangliqi1]

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

}

[RestlessBreeze]

code

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

[joemonkeylee]

var frequencySort = function(s) {
    const map = new Map();
    const length = s.length;
    for (let i = 0; i < length; i++) {
        const c = s[i];
        const frequency = (map.get(c) || 0) + 1;
        map.set(c, frequency);
    }
    const list = [...map.keys()];
    list.sort((a, b) => map.get(b) - map.get(a));
    const sb = [];
    const size = list.length;
    for (let i = 0; i < size; i++) {
        const c = list[i];
        const frequency = map.get(c);
        for (let j = 0; j < frequency; j++) {
            sb.push(c);
        }
    }
    return sb.join('');
};

[lp1506947671]

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为字符个数，KK为去重字符个数

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

• 空间复杂度：O(K)

[Jetery]

class Solution {
public:
    string frequencySort(string s) {
        unordered_map<char, int> hash;
        for (auto &c : s)
            hash[c]++;

        vector<pair<int, char>> chs;
        unordered_map<char, int>::iterator it;
        for (it = hash.begin(); it != hash.end(); it++)
            chs.push_back(make_pair(it -> second, it -> first));

        sort(chs.begin(), chs.end());
        reverse(chs.begin(), chs.end());

        string ans = "";
        for (auto &ch : chs)
            ans += string(ch.first, ch.second);

        return ans;
    }
};

[NorthSeacoder]

var frequencySort = function(s) {
    const heap = new maxHeap();
    const res = [];
    for (let i = 0; i < s.length; i++) {
        heap.push(s[i]);
    }
    for (let i = 0; i < s.length; i++) {
        res.push(heap.pop());
    }
    return res.join('');
};
class maxHeap {
    constructor() {
        this.heap = [0];
        this.set = new Set();
    }
    //大->上
    shiftUp(i) {
        while (i >> 1 > 0) {
            const parentI = i >> 1;
            const parent = this.heap[parentI];
            const cur = this.heap[i];
            if (cur[1] > parent[1]) {
                [this.heap[parentI], this.heap[i]] = [cur, parent];
            }
            i = parentI;
        }
    }
    getMaxChild(i) {
        const len = this.heap.length - 1;
        if (2 * i + 1 > len) return 2 * i;
        const left = this.heap[2 * i][1];
        const right = this.heap[2 * i + 1][1];
        if (left > right) return 2 * i;
        return 2 * i + 1;
    }
    //小->下
    shiftDown(i) {
        const len = this.heap.length - 1;
        while (2 * i <= len) {
            const childI = this.getMaxChild(i);
            const child = this.heap[childI];
            const cur = this.heap[i];
            if (cur[1] < child[1]) {
                [this.heap[childI], this.heap[i]] = [cur, child];
            }
            i = childI;
        }
    }

    push(val) {
        if (!this.set.has(val)) {
            this.heap.push([val, 1]);
            this.shiftUp(this.heap.length - 1);
            this.set.add(val);
        } else {
            const index = this.heap.findIndex((item) => item[0] === val);
            this.heap[index][1]++;
            this.shiftUp(index);
        }
    }

    pop() {
        if (this.heap.length === 1) return;
        if (this.heap[1][1] > 1) {
            this.heap[1][1]--;
            return this.heap[1][0];
        } else {
            const last = this.heap.length - 1;
            const res = this.heap[1][0];
            this.heap[1] = this.heap[last];
            this.heap.pop();
            this.shiftDown(1);
            this.set.delete(res);
            return res;
        }
    }
}

[yingchehu]

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

[kofzhang]

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