This is the first article I participated in beginners’ introduction

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' occurs twice, 'r' and 't' occur only once. So 'e' must come before 'r' and 't'. In addition, "EETR" is also a valid answer. Example 2: Input: "ccCAaa" Output: "ccCAaa" Explanation: both 'c' and 'a' occur three times. Also, "aaaccc" is a valid answer. Note that "cacaca" is incorrect because the same letters must be placed together. Example 3: Input: "Aabb" Output: "bbAa" Explanation: In addition, "bbAa" is also a valid answer, but "Aabb" is incorrect. Note that 'A' and 'A' are considered two different characters.Copy the code

Their thinking

  1. The string consists of 52 uppercase and lowercase letters and 10 numbers, so we can directly divide it into 62 buckets and use a two-dimensional array to record the elements and their occurrence times.

  2. Since the ASCII code for numbers, large and small letters is not contiguous, we need to divide it into three parts and parse it into contiguous arrays

  3. Then sort the number of occurrences.

code

class Solution {
    public String frequencySort(String s) {

        int n=s.length();
        int[][] cnt = new int[62] [2];
        for (int i=0; i<62; i++) cnt[i][0]=i;
        for (int i=0; i<n; i++) {if(s.charAt(i)>='0'&&s.charAt(i)<='9')
            cnt[s.charAt(i)-'0'+52] [1] + +;else
            cnt[s.charAt(i)-'a'> =0? s.charAt(i)-'a':s.charAt(i)-'A'+26] [1] + +; } Arrays.sort(cnt,(o1, o2) -> o2[1]-o1[1]);
        StringBuilder res = new StringBuilder();
        for (int i=0; i<52; i++) {for (int j=0; j<cnt[i][1]; j++) {if(cnt[i][0] > =52)
                    res.append((char) ('0'+cnt[i][0] -52));
                else 
                res.append((char)(cnt[i][0] > =26?'A'+cnt[i][0] -26:'a'+cnt[i][0])); }}returnres.toString(); }}Copy the code