leetcode451_根据字符出现频率排序。用java语言编写

题目描述：

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

示例 1:

输入:

"tree"

输出:

"eert"

解释:

'e'出现两次，'r'和't'都只出现一次。因此'e'必须出现在'r'和't'之前。此外，"eetr"也是一个有效的答案。

示例 2:

输入:

"cccaaa"

输出:

"cccaaa"

解释:

'c'和'a'都出现三次。此外，"aaaccc"也是有效的答案。注意"cacaca"是不正确的，因为相同的字母必须放在一起。

示例 3:

输入:

"Aabb"

输出:

"bbAa"

解释:

此外，"bbaA"也是一个有效的答案，但"Aabb"是不正确的。注意'A'和'a'被认为是两种不同的字符。

Java代码如下：

import java.util.*;

public class Solution {
    public String frequencySort(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        List<Map.Entry<Character, Integer>> list = new ArrayList<>(map.entrySet());
        Collections.sort(list, (o1, o2) -> o2.getValue() - o1.getValue());
        StringBuilder sb = new StringBuilder();
        for (Map.Entry<Character, Integer> entry : list) {
            char c = entry.getKey();
            int count = entry.getValue();
            for (int i = 0; i < count; i++) {
                sb.append(c);
            }
        }
        return sb.toString();
    }
}

解题思路：

首先遍历字符串，使用HashMap记录每个字符出现的次数。然后将HashMap转换为List，并按照出现次数从大到小进行排序。最后遍历排序后的List，将每个字符按照出现次数依次添加到StringBuilder中，并返回StringBuilder的字符串形式。

时间复杂度：O(nlogn)，其中n为字符串s的长度。遍历字符串的时间复杂度为O(n)，HashMap和List的操作时间复杂度均为O(n)，排序时间复杂度为O(nlogn)，StringBuilder操作时间复杂度为O(n)。因此总时间复杂度为O(nlogn)。

空间复杂度：O(n)，其中n为字符串s的长度。HashMap和List的空间复杂度均为O(n)，StringBuilder的空间复杂度也为O(n)。