Leetcode -451- Sort by the number of characters present

[Blog link]

The path to learning at 🐔

The nuggets home page

[Topic Description

Given a string, sort the characters in the string in descending order by frequency of occurrence. The sample1Input:"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. The sample2Input:"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. The sample3Input:"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. Related Topics Hash table String Bucket sort count Sort heap (priority queue) 👍283 👎 0
Copy the code

[答 案]

Leetcode topic link

[making address]

Code link

[introduction]

Idea 1: Map storage

• Stores the number of occurrences of each character according to map, and then sorts it by list
• This in turn is added to the new LinkedMap for output
• Can be optimized as an object so that you don’t have to reassign maps.

public String frequencySort(String s) {
            Map<Character, Integer> map = new TreeMap<>();
            char[] chars = s.toCharArray();
            for (Character c : chars
            ) {
                map.put(c, map.getOrDefault(c, 0) + 1);
            }
            String res = "";
            List<Map.Entry<Character,Integer>> list = new ArrayList<>(map.entrySet());
            list.sort(new Comparator<Map.Entry<Character, Integer>>() {
                @Override
                public int compare(Map.Entry<Character, Integer> o1, Map.Entry<Character, Integer> o2) {
                    returno2.getValue()- o1.getValue(); }}); Map<Character,Integer> map2 =new LinkedHashMap<>();
            for(Map.Entry<Character,Integer> entry: list){
                map2.put(entry.getKey(), entry.getValue());
            }
            for (Character c : map2.keySet()
            ) {
                for (int i = 0; i < map.get(c);i++){
                    res += c;
                }
            }
            return res;
        }
Copy the code

$Time complexity O(nlg_{n}))$

Idea 2: Simulate arrays

• ASCII characters are 128 bits, so a preconfigured array int[128][2]
• Then put the corresponding array bit according to index, nums[I][1] represents the number of occurrences

public String frequencySort(String s) {
            int[][] nums = new int[128] [2];
            for (int i = 0; i < 128; i++) {
                nums[i][0] = i;
            }
            for (Character c : s.toCharArray()) {
                nums[c][1] + +; } Arrays.sort(nums, (a, b) -> {if (a[1] != b[1]) {
                    return b[1] - a[1];
                }
                return a[0] - b[0];
            });
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < nums.length; i++) {
                if (nums[i][1] != 0) {
                    char c = (char) (nums[i][0]);
                    int cnt = nums[i][1];
                    while (cnt > 0) { sb.append(c); cnt--; }}}return sb.toString();
        }
Copy the code

$Time complexity O(n))$