azl397985856 commented 1 year ago

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'被认为是两种不同的字符。

tiandao043 commented 1 year ago

class Solution {
public:
    string frequencySort(string s) {
        unordered_map<char, int> ump;
        for (const auto ch : s) { ump[ch]++; }
        priority_queue<pair<int, char>> pq;
        for (const auto &m : ump) {
            pq.push({m.second, m.first});
        }        
        string ret;
        while (!pq.empty()) {
            auto t = pq.top(); 
            pq.pop();
            ret.append(t.first, t.second);
        }
        return ret;
    }
};

Jetery commented 1 year ago

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

Ryanbaiyansong commented 1 year ago

··· class Solution: def frequencySort(self, s: str) -> str: count = Counter(s) ss = list(reversed(sorted(count.keys(), key=lambda it:count[it]))) res = "" for ch in ss: res += count[ch] * ch

    return res

···

snmyj commented 1 year ago

  bool cmp(vector<int>a,vector<int>b){
            return a[1]==b[1]?a[0]<b[0]:a[1]<b[1];
        }

class Solution {
public:

    string frequencySort(string s) {

        unordered_map<int,int> m;
        vector<vector<int>> res;
        vector<int> temp={};
        string ans;
        for(int i=0;i<s.size();i++){
            m[s[i]]++;
        }
        for(auto x:m){
            temp.push_back(x.first-'a');
            temp.push_back(x.second);
            res.push_back(temp);
            temp={};    
        }

        sort(res.begin(),res.end(),cmp);
        reverse(res.begin(),res.end());
        for(int i=0;i<res.size();i++){
            int cnt=res[i][1];
            char c=res[i][0]+'a';
            for(int j=0;j<cnt;j++){
                ans+=c;
            }
        }
        return ans;

    }
};

klspta commented 1 year ago

class Solution {
    public String frequencySort(String s) {
        int[][] cnts = new int[128][2];

        for(int i = 0; i < 128; i++){
            cnts[i][0] = i;
        }

        char[] cs = s.toCharArray();

        for(char c : cs){
            cnts[c][1]++;
        }

        Arrays.sort(cnts, (a, b) -> a[1] == b[1] ? a[0] - b[0] : b[1] - a[1]);

        StringBuilder sb = new StringBuilder();

        for(int i = 0; i < 128; i++){
            char c = (char)cnts[i][0];
            int k = cnts[i][1];

            while(k-- > 0){
                sb.append(c);
            }
        }

        return sb.toString();
    }
}

guowei0223 commented 1 year ago

class Solution:
    def frequencySort(self, s: str) -> str:
        counts = collections.Counter(s)
        # print(counts)
        string_res = ""
        for letter, freq in counts.most_common():
        # letter * freq makes freq copies of letter.
        # e.g. "a" * 4 -> "aaaa"
           string_res+=letter * freq
        return string_res

Elsa-zhang commented 1 year ago

class Solution:
    def frequencySort(self, s: str) -> str:
        s_dict = {}
        for v in s:
            s_dict[v] = s_dict.get(v, 0)+1

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

        ans = ''
        for k,v in s_dict:
            ans+=k*v
        return ans

Abby-xu commented 1 year ago

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])

FlipN9 commented 1 year ago

/**
    TC: O(N)    SC: O(N)
*/
class Solution {
    public String frequencySort(String s) {
        int N = s.length();
        // 1. count all appearances
        int[] count = new int[128];
        for (char c : s.toCharArray()) {
            count[c]++;
        }
        // 2. use bucket to store char with same frequency
        List<Character>[] bucket = new List[N + 1];
        for (int i = 0; i < 128; i++) {
            int freq = count[i];
            if (freq == 0) continue;
            if (bucket[freq] == null) 
                bucket[freq] = new ArrayList<>();
            bucket[freq].add((char) i);
        }
        // 3. generate res
        char[] res = new char[N];
        int idx = 0;
        for (int freq = N; freq > 0; freq--) {
            List<Character> cur = bucket[freq];
            if (cur == null) continue;
            for (Character c : cur) {
                for (int i = freq; i > 0; i--)
                    res[idx++] = c;
            }
            if (idx == N) break;
        }
        return new String(res);
    }
}

mayloveless commented 1 year ago

思路

大顶堆

代码

/**
 * @param {string} s
 * @return {string}
 */
var frequencySort = function(s) {
    const map = {};
    for(let i=0;i<s.length;i++) {
        map[s[i]] = (map[s[i]] ?? 0) + 1;
    }

    const maxQ = new MaxPriorityQueue({
        priority: node => node.val
    });
    for(let key in map) {
       maxQ.enqueue({
           str: key,
           val: map[key],
       });
    }

    let res = ''
    while(!maxQ.isEmpty()) {
        const ch = maxQ.dequeue().element.str;
        res += ch.repeat(map[ch]);
    }
    return res;
};

复杂度

时间：O(n+klogk) 空间：O(k)

paopaohua commented 1 year ago

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

RestlessBreeze commented 1 year ago

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

bookyue commented 1 year ago

code

    public String frequencySort(String s) {
        Map<Character, Integer> freq = new HashMap<>();
        for (int i = 0; i < s.length(); i++)
            freq.merge(s.charAt(i), 1, Integer::sum);

        var pq = new PriorityQueue<Map.Entry<Character, Integer>>(Comparator.comparingInt(i -> -i.getValue()));
        pq.addAll(freq.entrySet());
        StringBuilder sb = new StringBuilder();
        while (!pq.isEmpty()) {
            var e = pq.poll();
            sb.append(e.getKey().toString().repeat(e.getValue()));
        }

        return sb.toString();
    }

whoam-challenge commented 1 year ago

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() res += key * (-val) return res

Elon-Lau commented 1 year ago