字符串出现频率排序java_LeetCode 451. Sort Characters By Frequency 根据字符出现频率排序 (C++/Java)...

题目：

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.

分析：

给定一个字符串，请将字符串里的字符按照出现的频率降序排列。

基本思路就是遍历一遍字符串，将字符出现的次数存进Hashmap中，再遍历一遍Hashmap将字符和出现次数作为一组pair存进优先级队列中，再从队列中依次取出数据拼接成最后的字符串。

程序：

C++

classSolution {public:string frequencySort(strings) {

unordered_mapm;for(const auto&c:s)

m[c]++;

priority_queue, vector>, cmp >q;for(const auto&i:m){

q.push(make_pair(i.first, i.second));

}string res = "";while(!q.empty()){

res.append(q.top().second, q.top().first);

q.pop();

}returnres;

}private:structcmp{bool operator() (pair a, pairb)

{return a.second

}

};

};

Java

classSolution {publicString frequencySort(String s) {for(charc:s.toCharArray()){

map.put(c, map.getOrDefault(c,0) + 1);

}

p.addAll(map.entrySet());while(!p.isEmpty()){

Map.Entry e =p.poll();for(int i = 0; i < e.getValue().intValue(); i++){

res.append(e.getKey());

}

}returnres.toString();

}private StringBuilder res = newStringBuilder();private HashMap map = new HashMap<>();private PriorityQueue> p = new PriorityQueue<>(new Comparator>()

{public int compare(Map.Entry a, Map.Entryb)

{return b.getValue() -a.getValue();

}

});

}