排序
这道题只关心
o
r
d
e
r
order
order 出现的字符,在
s
s
s 中的排序。
s
s
s 中不在
o
r
d
e
r
order
order 的字符,在排序后是什么位置,不影响答案。
可以用
s
o
r
t
sort
sort 函数,传入我们自定义的排序方式,按照
o
r
d
e
r
order
order 中字母顺序排序。
更贴切的,可以用计数排序,统计
s
s
s 中每个字母出现次数
t
i
m
e
s
times
times。按照
o
r
d
e
r
order
order 的循序,和
t
i
m
e
s
times
times 的次数,依次将每个字母加入
a
n
s
ans
ans , 最后将剩余字符加入
a
n
s
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;
}
};
计数排序
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;
}
};
博主致语
理解思路很重要!
欢迎读者在评论区留言,作为日更博主,看到就会回复的。
AC
复杂度分析
自定义排序
- 时间复杂度: O ( n l o g n + ∣ C ∣ ) O(nlogn + |C|) O(nlogn+∣C∣), n n n 是 s s s 的长度, ∣ C ∣ = 26 |C|=26 ∣C∣=26 是字母个数。快排 s s s 的时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn) ,遍历 26 26 26 个字母的时间复杂度 O ( ∣ C ∣ ) O(|C|) O(∣C∣) 。
- 空间复杂度: O ( ∣ C ∣ ) O(|C|) O(∣C∣), c m p cmp cmp 数组的空间复杂度是 O ( ∣ C ∣ ) O(|C|) O(∣C∣) 。
计数排序
- 时间复杂度: O ( n + ∣ C ∣ ) O(n + |C|) O(n+∣C∣), n n n 是 s s s 的长度, ∣ C ∣ = 26 |C|=26 ∣C∣=26 是字母个数。一次遍历 s s s 并计数的时间复杂度 O ( n ) O(n) O(n) ,遍历 26 26 26 个字母的时间复杂度 O ( ∣ C ∣ ) O(|C|) O(∣C∣) 。
- 空间复杂度: O ( ∣ C ∣ ) O(|C|) O(∣C∣), t i m e s times times 数组的空间复杂度是 O ( ∣ C ∣ ) O(|C|) O(∣C∣) 。