力扣(LeetCode)791. 自定义字符串排序(C++)

排序

这道题只关心 $order$ 出现的字符，在 $s$ 中的排序。 $s$ 中不在 $order$ 的字符，在排序后是什么位置，不影响答案。
可以用 $sort$ 函数，传入我们自定义的排序方式，按照 $order$ 中字母顺序排序。
更贴切的，可以用计数排序，统计 $s$ 中每个字母出现次数 $times$。按照 $order$ 的循序，和 $times$ 的次数，依次将每个字母加入 $ans$ , 最后将剩余字符加入 $ans$，即为所求。

代码展示

自定义排序

class Solution {
public:
    string customSortString(string order, string s) {
        //自定义字符串排序
        vector<int> cmp(26);
        for(int i = 0 ;i<order.size();i++){
            cmp[order[i]-'a'] = i+1;//每个字母的顺序
        }
        sort(s.begin(),s.end(),[&](char c0,char c1){//匿名表达式
            return cmp[c0-'a'] < cmp[c1-'a'];//自定义顺序
        });
        return s;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

计数排序

class Solution {
public:
    string customSortString(string order, string s) {
        //计数排序
        vector<int> times(26);
        for(auto x:s){//记录s中每个字母出现的次数
            times[x-'a'] ++;//每个字母的顺序
        }
        string ans;
        for(auto x:order){
            while(times[x-'a']>0){//ans+=string(times[x-'a'],x);
                ans+=x;
                times[x-'a']--;//time[x-'a'] = 0;
            }
        }
        for(int i = 0;i<26;i++){//剩余顺序无所谓，关键在于排序order
            ans+=string(times[i],i+'a');
            times[i] = 0;
        }
        // for(auto x:s){
        //     ans+=string(times[x-'a'],x);
        //     times[x-'a'] = 0;
        // }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

博主致语

理解思路很重要！
欢迎读者在评论区留言，作为日更博主，看到就会回复的。

AC

复杂度分析

自定义排序

1. 时间复杂度: $O(nlogn+|C|)$， $n$ 是 $s$ 的长度，$|C|=26$ 是字母个数。快排 $s$ 的时间复杂度 $O(nlogn)$ ，遍历 $26$ 个字母的时间复杂度 $O(|C|)$ 。
2. 空间复杂度: $O(|C|)$，$cmp$ 数组的空间复杂度是 $O(|C|)$ 。

计数排序

1. 时间复杂度: $O(n+|C|)$， $n$ 是 $s$ 的长度，$|C|=26$ 是字母个数。一次遍历 $s$ 并计数的时间复杂度 $O(n)$ ，遍历 $26$ 个字母的时间复杂度 $O(|C|)$ 。
2. 空间复杂度: $O(|C|)$，$times$ 数组的空间复杂度是 $O(|C|)$ 。