题目

给你一个下标从 0 开始的字符串 s ，将 s 中的元素重新 排列 得到新的字符串 t ，它满足：

• 所有辅音字母都在原来的位置上。更正式的，如果满足 0 <= i < s.length 的下标 i 处的 s[i] 是个辅音字母，那么 t[i] = s[i] 。
• 元音字母都必须以他们的 ASCII 值按 非递减 顺序排列。更正式的，对于满足 0 <= i < j < s.length 的下标 i 和 j  ，如果 s[i] 和 s[j] 都是元音字母，那么 t[i] 的 ASCII 值不能大于 t[j] 的 ASCII 值。

请你返回结果字母串。

元音字母为 'a' ，'e' ，'i' ，'o' 和 'u' ，它们可能是小写字母也可能是大写字母，辅音字母是除了这 5 个字母以外的所有字母。

示例 1：

输入：s = "lEetcOde" 输出："lEOtcede" 解释：'E' ，'O' 和 'e' 是 s 中的元音字母，'l' ，'t' ，'c' 和 'd' 是所有的辅音。将元音字母按照 ASCII 值排序，辅音字母留在原地。

示例 2：

输入：s = "lYmpH" 输出："lYmpH" 解释：s 中没有元音字母（s 中都为辅音字母），所以我们返回 "lYmpH" 。

解题思路

题目的核心要求是：辅音字母的位置不变，元音字母按照ASCII码值从小到大，填充到原来所有元音字母的位置上。

这就意味着，我们可以把辅音和元音分开处理。辅音构成了整个字符串的“骨架”，是固定不变的。我们要做的是把所有的“血肉”（元音）抽出来，排好序，再按顺序填回到“骨架”中属于元音的那些空位上。

具体的分步实现：

1. 第一步：识别并提取所有元音字母
   • 创建一个空的列表（或动态数组）为 vowels。
   • 遍历一遍输入的字符串 s。
   • 对于 s 中的每一个字符，判断它是否是元音字母（'a', 'e', 'i', 'o', 'u'，包括大小写）。
   • 如果是元音字母，就将它添加到 vowels 列表中。
2. 第二步：对提取出的元音字母进行排序
   • 将 vowels 列表按照 ASCII 值的非递减顺序进行排序。
   • 大多数编程语言的内置排序函数对字符列表进行排序时，默认就是按照 ASCII 值（或 Unicode 码点）来的，所以直接调用标准排序即可。
3. 第三步：将排序后的元音放回原字符串的元音位置
   • 将原字符串 s 转换为一个可修改的序列，比如字符数组（char[]）或字符列表，我们称之为 result_list。这样做是为了方便修改指定位置的字符。
   • 创建一个指针（或索引变量），比如 vowel_idx = 0，用于追踪 vowels 列表中当前要使用的元音。
   • 再次遍历原字符串 s 的每个位置（从索引 0 到 s.length - 1）。
   • 在遍历过程中，再次判断当前位置 i 的原始字符 s[i] 是否是元音。
   • 如果 s[i] 是一个元音，说明这个位置需要被替换。此时，我们将 result_list[i] 的值更新为排序后元音列表 vowels 中的第 vowel_idx 个元素。
   • 然后，将 vowel_idx 加一，准备填充下一个元音位置。
   • 如果 s[i] 是一个辅音，result_list[i] 的值保持不变。
   • 遍历结束后，result_list 中就存放着我们想要的结果。
4. 第四步：生成最终结果
   • 将 result_list（字符数组或列表）转换回字符串，并返回。

优化思路

1. 采用计数排序的思想，我们其实不关心我们第一次读取元音字母的顺序，所以可以只计数，然后在第二次输出的时候进行元音从小到大的输出即可。
2. 那么可以采取的思路有两条，一条是使用能自动排序的数据结构，这里可以考虑 map ，可以在计数元音的同时进行排序，一举两得。
3. 另外一个思路是使用 vector 计数即可，只要 vector 空间大于ASCII编码值的最大，就可以把索引当空间直接计数，最后再用一个引导string从小到大导出我们想要的值就行了。

优化一代码：使用 map

class Solution {
public:
    string sortVowels(const string& s) {
        
        unordered_set<char> vowels = {'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'};

        map<char, int> vowel_counts;
        for(const char& letter : s)
        {
            if(vowels.count(letter))
            {
                vowel_counts[letter]++;
            }
        }

        string ans = "";
        auto it = vowel_counts.begin(); // 获取指向最小元音的迭代器

        for(char letter : s)
        {
            if(vowels.count(letter))
            {
                ans += it->first;
                it->second--;
                if (it->second == 0)
                {
                    it++;
                }
            }
            else
            {
                // 如果是辅音，直接添加
                ans += letter;
            }
        }
        return ans;
    }
};

• 时间复杂度: O(N)
  • 第一次遍历 (计数)：遍历了一次字符串（长度为 N）。在循环内部，vowels.count() 在 unordered_set中查询是 O(1) 的。vowel_counts[letter]++ 操作 std::map，其复杂度为 O(logK)，其中 K 是 map 中键的数量。因为元音字母的数量是固定的（最多10个），所以 K 是一个很小的常数，O(logK) 实际上就是 O(1)。因此，第一次遍历的总时间是 N×O(1)=O(N)。
  • 第二次遍历 (构建字符串)：再次遍历字符串（长度为 N）。循环内部的操作，如访问 map 迭代器、+= 追加字符（均摊 O(1)），都是常数时间操作。因此，第二次遍历的总时间也是 O(N)。
  • 总计: O(N)+O(N)=O(N)。
• 空间复杂度: O(N)
  • unordered_set<char> vowels：存储常数个（10个）元音，空间复杂度为 O(1)。
  • map<char, int> vowel_counts：最多存储10个键值对，空间复杂度为 O(1)。
  • string ans：需要一个和输入字符串等长的额外字符串来存储结果，空间复杂度为 O(N)。
  • 总计: 主要由结果字符串 ans 决定，为 O(N)。

优化二代码：使用 vector

class Solution {
public:
    string sortVowels(const string& s) {
        // 优化1：使用一个大小为 128 的数组来代替 map
        // 数组的索引直接对应字符的 ASCII 码
        int vowel_counts[128] = {0};
        
        // C++中判断元音更快的方式可能是 switch-case 或者直接查找字符串
        auto is_vowel = [](char c) {
            return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' ||
                   c == 'A' || c == 'E' || c == 'I' || c == 'O' || c == 'U';
        };

        // 第一次遍历：计数所有元音
        for (char letter : s) {
            if (is_vowel(letter)) {
                vowel_counts[letter]++;
            }
        }
        
        // 优化2：创建副本并原地修改，而不是动态拼接
        string ans = s;
        
        // 定义一个有序的元音字符串，用于按顺序填充
        const string sorted_vowels = "AEIOUaeiou";
        int vowel_idx = 0; // 指向 sorted_vowels 的索引

        // 第二次遍历：填充元音
        for (int i = 0; i < ans.length(); ++i) {
            if (is_vowel(ans[i])) {
                // 找到下一个还有剩余数量的元音
                while (vowel_counts[sorted_vowels[vowel_idx]] == 0) {
                    vowel_idx++;
                }
                
                // 替换当前位置的元音
                ans[i] = sorted_vowels[vowel_idx];
                // 消耗掉一个元音
                vowel_counts[sorted_vowels[vowel_idx]]--;
            }
        }
        
        return ans;
    }
};

• 时间复杂度: O(N)
  • 第一次遍历 (计数)：遍历一次字符串（长度为 N）。在循环内部，is_vowel() 是常数次比较，是 O(1)。vowel_counts[letter]++ 是数组的随机访问，也是 O(1)。因此，第一次遍历的总时间是 N×O(1)=O(N)。
  • 第二次遍历 (填充字符串)：再次遍历字符串（长度为 N）。循环内部的 while 循环看起来可能会增加复杂度，但 vowel_idx 这个指针在整个过程中只会从头到尾遍历 sorted_vowels 字符串（长度为10）一次，所以所有 while 循环的总操作数是一个常数。因此，均摊到每次循环中，操作也是 O(1) 的。第二次遍历的总时间是 O(N)。
  • 总计: O(N)+O(N)=O(N)。
• 空间复杂度: O(N)
  • int vowel_counts[128]：一个大小固定的数组，空间复杂度为 O(1)。
  • string ans = s：创建了输入字符串的一个副本，空间复杂度为 O(N)。
  • 总计: 主要由结果字符串副本 ans 决定，为 O(N)。