2021-07-03 LeetCode problem of the Day

Link: leetcode-cn.com/problems/so…

Tags: Hash table, String, bucket sort, Count, Sort, heap (priority queue)

The title

Given a string, sort the characters in the string in descending order by frequency of occurrence.

Example 1:

Input:"tree"Output:"eert"Explanation:'e'It happens twice,'r'and't'They only show up once. so'e'Must be present at'r'and't'Before. In addition,"eetr"It's also a valid answer.Copy the code

Example 2:

Input:"cccaaa"Output:"cccaaa"Explanation:'c'and'a'All three times. In addition,"aaaccc"It's also a valid answer. Pay attention to"cacaca"Is incorrect because the same letters must be placed together.Copy the code

Example 3:

Input:"Aabb"Output:"bbAa"Explanation: In addition,"bbaA"It's also a valid answer, but"Aabb"Is not true. Pay attention to'A'and'a'Are considered to be two different characters.Copy the code

The title

There are many ways to do this

Method 1: Use a hash table to record the number of occurrences of each character, and then sort it in descending order. Finally, concatenate it into a string and return it. Since I’m using characters as keys and occurrences as values, there’s no need to use TreeMap data structures and go straight to HashMap because you’re going to sort by value at the end.

Method 2: use a two-dimensional array to solve, because the range of characters is in [0, 127], so you can use a two-dimensional array of 128 length, record the characters and the number of occurrences, and then sort.

coding

Hash table:

class Solution {
    public String frequencySort(String s) {
        Map<Character, Integer> map = new HashMap<>();
        char[] chs = s.toCharArray();
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < chs.length; i++) {
            map.put(chs[i], map.getOrDefault(chs[i], 0) + 1);
        }
        // Descending by value
        List<Map.Entry<Character, Integer>> list = new ArrayList<>(map.entrySet());
        Collections.sort(list, (o1, o2) -> {
            return o2.getValue().compareTo(o1.getValue());
        });

        for (Map.Entry<Character, Integer> entry : list) {
            int count = entry.getValue();
            Character c = entry.getKey();
            for (int i = 0; i < count; i++) { sb.append(c); }}returnsb.toString(); }}Copy the code

Array:

class Solution {
    public String frequencySort(String s) {
        int[][] vals = new int[128] [2];
        char[] chs = s.toCharArray();
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < chs.length; i++) {
            vals[chs[i]][0] = chs[i];
            vals[chs[i]][1] + +; } Arrays.sort(vals, (a, b) -> {if (a[1] != b[1]) {
                return b[1] - a[1];
            }
            return a[0] - b[0];
        });

        for (int i = 0; i < vals.length; i++) {
            int[] val = vals[i];
            while (val[1]-- > 0) {
                sb.append((char)val[0]); }}returnsb.toString(); }}Copy the code