这题考查的是排序吧… 还有rbegin的使用。
普通排序:时间 O(nlogn) / 空间 O(1)
前半部分顺序排序,后半部分逆序排序。
1 2 3 4 5 6 7 8 9 |
class Solution { public: string smallestPalindrome(string s) { const int n = s.length(); sort(begin(s), begin(s) + n / 2); sort(rbegin(s), rbegin(s) + n / 2); return s; } }; |
计数排序:时间:O(n),空间:O(n) -> O(1)
首尾一起写
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
// 7 ms, 54.65MB class Solution { public: string smallestPalindrome(string s) { vector<int> f(128); for (size_t i = 0; i < s.size() / 2; ++i) ++f[s[i]]; auto h=begin(s); auto t=rbegin(s); for (char c = 'a'; c <= 'z'; ++c) while (f[c]--) *h++ = *t++ = c; return s; } }; |