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.
一刷
題解：
O(nlogn), 比較型sort
class Solution {
class Entry{
char ch;
int count;
public Entry(){
this.count = 0;
}
}
public String frequencySort(String s) {
if(s == null || s.length()<=1) return s;
Entry[] freq = new Entry[256];
for(int i=0; i<256; i++){
freq[i] = new Entry();
}
for(int i=0; i<s.length(); i++){
char c = s.charAt(i);
freq[c].ch = c;
freq[c].count++;
}
Arrays.sort(freq, (a,b)->b.count-a.count);
StringBuilder res = new StringBuilder();
for(int i=0; i<freq.length; i++){
if(freq[i].count!=0){
while(freq[i].count>0) {
freq[i].count--;
res.append(freq[i].ch);
}
}
}
return res.toString();
}
}
follow up: 如果count一樣览绿，按照在字符串中出現(xiàn)順序輸出：解決方案，在entry中添加一個(gè)appear(第一次出現(xiàn)時(shí)char index)順序域, sort時(shí)可很，如果count一樣纤子，appear小的在前臼予。
class Solution {
class Entry{
char ch;
int count;
int appear;
public Entry(){
this.count = 0;
}
}
public String frequencySort(String s) {
if(s == null || s.length()<=1) return s;
Entry[] freq = new Entry[256];
for(int i=0; i<256; i++){
freq[i] = new Entry();
}
for(int i=0; i<s.length(); i++){
char c = s.charAt(i);
freq[c].ch = c;
if(freq[c].count == 0) freq[c].appear = i;
freq[c].count++;
}
Arrays.sort(freq, (a,b)->b.count == a.count? (a.appear - b.appear):(b.count - a.count));
StringBuilder res = new StringBuilder();
for(int i=0; i<freq.length; i++){
if(freq[i].count!=0){
while(freq[i].count>0) {
freq[i].count--;
res.append(freq[i].ch);
}
}
}
return res.toString();
}
}
O(n)的方法掉瞳， bucketsort
public String frequencySort(String s) {
if (s == null) {
return null;
}
//character->count
Map<Character, Integer> map = new HashMap();
char[] charArray = s.toCharArray();
int max = 0;
for (Character c : charArray) {
if (!map.containsKey(c)) {
map.put(c, 0);
}
map.put(c, map.get(c) + 1);
max = Math.max(max, map.get(c));
}
List<Character>[] array = buildArray(map, max);
return buildString(array);
}
private List<Character>[] buildArray(Map<Character, Integer> map, int maxCount) {
List<Character>[] array = new List[maxCount + 1];
for (Character c : map.keySet()) {
int count = map.get(c);
if (array[count] == null) {
array[count] = new ArrayList();
}
array[count].add(c);
}
return array;
}
private String buildString(List<Character>[] array) {
StringBuilder sb = new StringBuilder();
for (int i = array.length - 1; i > 0; i--) {
List<Character> list = array[i];
if (list != null) {
for (Character c : list) {
for (int j = 0; j < i; j++) {
sb.append(c);
}
}
}
}
return sb.toString();
}
另一種角度的bucketsort
map<Integer, List<Character>>, count->characters
class Solution {
public String frequencySort(String s) {
int max = 0;
char[] arr = s.toCharArray();
int[] count = new int[256];
for(char c : arr) count[c]++;
Map<Integer, List<Character>> map = new HashMap<>();//count->characters
for(int i=0; i<256; i++){
if(count[i]!=0){
int cn = count[i];
if(!map.containsKey(cn)){
map.put(cn, new ArrayList<Character>());
}
map.get(cn).add((char)i);
max = Math.max(max, cn);
}
}
StringBuilder sb = new StringBuilder();
for(int cnt = max; cnt>0; cnt--){//the maximum count is
if(map.containsKey(cnt)){
List<Character> val = map.get(cnt);
for(char ch : val){
for(int i=0; i<cnt; i++) sb.append(ch);
}
}
}
return sb.toString();
}
}
