Leetcode 791 Custom Sort String
题意：给定两个字符串，第一个字符串order，给定字符出现的先后顺序。 第二个字符串需要按照第一个字符串的顺序重新排列。没有在order字符串中出现的数组随意排列
https://leetcode.com/problems/custom-sort-string/
解答：先根据第二个字符串计算得到频率map，然后遍历order（确保有序), 根据频率map构建新的字符串，并且频率相应更新。当遍历到order字符串末尾后，加上此时频率map中不为0的那些字符。
class Solution {
public:
string customSortString(string order, string s) {
unordered_map<char, int> mp;
string res;
for(char ch : s) {
mp[ch]++;
}
for(char ch : order) {
while (mp.count(ch) && mp[ch] != 0) {
res += ch;
mp[ch]--;
}
}
for(auto& [k,v] : mp) {
while(mp[k] != 0) {
res += k;
mp[k]--;
}
}
return res;
}
};
时间复杂度
O
(
n
)
O(n)
O(n)
n
n
n是字符串的长度
空间复杂度
O
(
n
)
O(n)
O(n),频率数组有开销