题目:
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.
分析
方法1 bucket sort
public String frequencySort(String s) {
HashMap<Character, Integer> freqMap = new HashMap<Character, Integer>();
List<Character> [] bucket = new List[s.length() + 1];
StringBuilder sb = new StringBuilder();
for(int i = 0; i < s.length(); i++) {
Character c = s.charAt(i);
Integer freq = freqMap.get(c);
freqMap.put(c, 1 + ((freq == null)?0:freq));
}
for(char key : freqMap.keySet()) {
int val = freqMap.get(key);
if(bucket[val] == null)
bucket[val] = new ArrayList<Character>();
bucket[val].add(key);
}
for(int i = bucket.length - 1; i >= 0; i--) {
if(bucket[i] != null) {
for(char c : bucket[i]) {
for(int j = 0; j < i; j++)
sb.append(c);
}
}
}
return sb.toString();
}
方法2 priority queue
class CharacterFreq implements Comparable<CharacterFreq> {
Character c;
Integer freq;
public CharacterFreq(Character c, int freq) {
this.c = c;
this.freq = freq;
}
@Override
public int compareTo(CharacterFreq cf) {
return -freq.compareTo(cf.freq);
}
}
public String frequencySort(String s) {
HashMap<Character, Integer> freqMap = new HashMap<Character, Integer>();
for(int i = 0; i < s.length(); i++) {
Character c = s.charAt(i);
Integer freq = freqMap.get(c);
if(freq == null)
freqMap.put(c, 1);
else
freqMap.put(c, freq+1);
}
PriorityQueue<CharacterFreq> q = new PriorityQueue<CharacterFreq>();
for (Character k : freqMap.keySet()) {
q.add(new CharacterFreq(k, freqMap.get(k)));
}
StringBuilder sb = new StringBuilder();
s = "";
while(!q.isEmpty()) {
CharacterFreq cf = q.poll();
int freq = cf.freq;
for(int j = 0; j < freq; j++) {
sb.append(cf.c);
}
}
return sb.toString();
}
后者的效率是O(nlogn)，前者的效率是O(n)
另外，要注意的是，涉及string的题目，最好用StringBuilder，不然会超时
