自定义字符串排序

题目链接

自定义字符串排序

题目描述

注意

• 1 <= order.length <= 26
• order 和 s 由小写英文字母组成
• order 中的所有字符都 不同

解答思路

• 因为本题中需要排序的为小写字母，其在order中不重复，也就是需要排序的数量最多有26个，基数很小，所以可以使用计数排序
• 将s中的字符及其数量存储到数据结构中，使用一个大小为26的数组即可，再对order进行遍历，将相应数量的相应字符添加到新的字符串中，最终得到的就是排序后的字符串

代码

方法一：

class Solution {
    public String customSortString(String order, String s) {
        int[] count = new int[26];
        // 对s中出现大的字符进行计数
        for(char c : s.toCharArray()) {
            count[c - 'a'] += 1;
        }
        StringBuilder sb = new StringBuilder();
        for(char c : order.toCharArray()) {
            while(count[c - 'a'] > 0) {
                sb.append(c);
                count[c - 'a']--;
            }
        }
        for(int i = 0; i < count.length; i++) {
            while(count[i] != 0) {
                sb.append((char) (i + 'a'));
                count[i]--;
            }
        }
        return sb.toString();
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

关键点

• 计数排序的思想