首页 > 代码库 > 451. Sort Characters By Frequency

451. Sort Characters By Frequency

2024-08-23 08:13:46   218人阅读

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 sort in Map.Entry<>
public class Solution {
    public String frequencySort(String s) {
        HashMap<Character, Integer> map = new HashMap<>();
        for(int i = 0; i < s.length(); i ++){
            map.put(s.charAt(i), map.getOrDefault(s.charAt(i), 0) + 1);
        }
        ArrayList<Map.Entry<Character, Integer>> set = new ArrayList<Map.Entry<Character, Integer>>(map.entrySet());
        Collections.sort(set, new Comparator<Map.Entry<Character, Integer>>(){
             public int compare(Map.Entry<Character, Integer> v1, Map.Entry<Character, Integer> v2){
                 return v2.getValue()-v1.getValue();
             }
            });
        StringBuilder sb = new StringBuilder();
        for(Map.Entry<Character, Integer> k : set){
            int v = k.getValue();
            for(int i = 0 ; i < v ; i++){
                sb.append(k.getKey().toString());
            }
        }
        return sb.toString();
    }
}

 

451. Sort Characters By Frequency


联系
我们