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

女爷i 2022-12-30 03:49 134阅读 0赞

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

Given a string, sort it in decreasing order based on the frequency of characters.

**Example 1:**

Input:
    "tree"
    
    Output:
    "eert"
    
    Explanation:
    'e' appears twice while 'r' and 't' both appear once.
    So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.

**Example 2:**

Input:
    "cccaaa"
    
    Output:
    "cccaaa"
    
    Explanation:
    Both 'c' and 'a' appear three times, so "aaaccc" is also a valid answer.
    Note that "cacaca" is incorrect, as the same characters must be together.

**Example 3:**

Input:
    "Aabb"
    
    Output:
    "bbAa"
    
    Explanation:
    "bbaA" is also a valid answer, but "Aabb" is incorrect.
    Note that 'A' and 'a' are treated as two different characters.

# 思路与代码 #

执行用时：5 ms, 在所有 Java 提交中击败了96.24%的用户

内存消耗：39.4 MB, 在所有 Java 提交中击败了66.78%的用户

## java代码 ##

class Solution { 
        public String frequencySort(String s) { 
        	char[] arr = s.toCharArray();
        	int[] map = new int[128];
        	//统计字符在字母表出现的频率 Character_index---frequency
        	for (int i = 0; i < arr.length; i++) { 
        		int c = arr[i];
        		map[c] += 1;
    		}
        	//转化为 index---Character---frequency
        	List<Pair> list = new ArrayList<Pair>();
        	for (int i = 0; i < map.length; i++) { 
    			if(map[i]!=0) { 
    				list.add(new Pair((char) i, map[i]));
    			}
    		}
        	//用JDK8 Comparator排序
        	list.sort((a,b)->b.frequency-a.frequency);
        	//返回字符串
        	StringBuffer buf = new StringBuffer();
        	for (int i = 0; i < list.size(); i++) { 
        		Pair p = list.get(i);
    			int n = p.frequency;
    			do { 
    				buf.append(p.ch);
    			} while (--n>0);
    		}
        	return buf.toString();
        }
        
        class Pair { 
            char ch;
            int frequency;
    
            Pair(char ch, int frequency) { 
                this.ch = ch;
                this.frequency = frequency;
            }
        }
    }

## cpp代码 ##

#include <vector>
    #include <iostream>
    #include <queue>
    #include <unordered_map>
    #include <string>
    #include <algorithm>
    #include "common.h"
    
    using namespace std;
    
    typedef std::pair<int, int> Pair;
    
    auto greaterPair = [](Pair a, Pair b) -> bool { 
    	return a.second > b.second;
    };
    
    void sortPair(vector<Pair>& vec) { 
    	sort(vec.begin(), vec.end(), greaterPair);
    }
    
    //方法一：按照出现频率排序
    class Solution { 
    public:
    	string frequencySort(string s) { 
    		int cnt[128] = {  0 };
    		for (auto c : s) ++cnt[int(c)];
    		vector<pair<int, int>> vec;
    		for (int i = 0; i < 128; ++i) { 
    			if (cnt[i] > 0) vec.push_back({  i, cnt[i] });
    		}
    		auto greater = [](pair<int, int> a, pair<int, int> b) -> bool { 
    			return a.second > b.second;
    		};
    		sort(vec.begin(), vec.end(), greater);
    		s = "";
    		for (auto p : vec) { 
    			for (int i = 0; i < p.second; ++i) s += char(p.first);
    		}
    		return s;
    	}
    };
    
    //方法一：按照出现频率排序
    class Solution2 { 
    public:
    	string frequencySort(string s) { 
    		int cnt[128] = {  0 };
    		for (auto c : s) ++cnt[int(c)];
    		vector<Pair> vec;
    		for (int i = 0; i < 128; ++i) { 
    			if (cnt[i] > 0) vec.push_back({  i, cnt[i] });
    		}
    		sortPair(vec);
    		s = "";
    		for (auto p : vec) { 
    			for (int i = 0; i < p.second; ++i) s += char(p.first);
    		}
    		return s;
    	}
    };
    
    //方法二：桶排序
    class Solution3 { 
    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;
    	}
    };
    
    
    //https://leetcode-cn.com/u/great-boyd2rt/
    
    int main() { 
    	string str = "Aabb";
    	Solution2 s;
    	cout << s.frequencySort(str) << endl;
    }