将字符串中的元音字母排序 图解题解

把元音抠出来重排，辅音要放回哪里

给一个下标从 0 开始的字符串 s，元音是 a e i o u、大写小写都算，其余全是辅音。要重排成新串：辅音留在原来的下标一个都不挪，元音则按 ASCII 值从小到大重新排好。题面例子 s=lEetcOde，元音在下标 1、2、5、7，依次是 E e O e，排好塞回去得到 lEOtcede；再看 s=lYmpH，一个元音都没有，原样返回。

元音散在辅音中间，挨个交换为什么容易乱

难点在元音是散落的：lEetcOde 里下标 1、2、5、7 才是元音，中间夹着辅音 l t c d。若想在原串上两两比较元音、谁小就换过去，每挪一步都得重新数哪些位置是元音、跳过中间的辅音，下标来回错位，稍不留神连辅音也被换动。而且这种相邻交换本质是冒泡，最坏要比 O(n²) 次。

辅音钉死、元音单飞：收集、排序、回填三步

既然辅音全程待在原地，它们放哪跟元音怎么排毫无关系，干脆先把它们当背景。做法分三步：先从左扫一遍，把所有元音按遇到的先后抠进一个单独的篮子，辅音只记住位置；再对篮子里这几个元音排序；最后从头再扫一遍，碰到辅音原样照抄，碰到元音位置就从排好的篮子里从左往右依次取一个填进去。两趟扫描加中间一次排序，元音和辅音就干净分开了。

排序按 ASCII 不按字母表，大写为什么排在小写前

排序这一步有个坑：比的是 ASCII 值，不是字母表顺序。ASCII 里大写字母 A 到 Z 是 65 到 90，小写 a 到 z 是 97 到 122，所以任意大写字母都小于任意小写字母。篮子里 E 是 69、O 是 79、两个 e 都是 101，按 ASCII 从小到大就排成 E、O、e、e，大写的 E、O 反而站在小写 e 前面。若把 E 和 e 当同一个字母、按字母表比就会排错。判元音时可以先转小写再看，但排序时要用字符本身的 ASCII。

lEetcOde 走一遍，四个元音怎么各自归位

从左扫 lEetcOde：下标 1 收 E、下标 2 收 e、下标 5 收 O、下标 7 收 e，篮子按先后是 E e O e，ASCII 依次 69、101、79、101，辅音 l t c d 分别钉在下标 0、3、4、6。给篮子排序得到 69、79、101、101，也就是 E、O、e、e。再从头回填：下标 0 辅音 l 照抄；下标 1 取 E；下标 2 取 O，原来的 e 被换掉；下标 3、4 辅音 t、c 照抄；下标 5 取 e；下标 6 辅音 d 照抄；下标 7 取最后一个 e。拼起来正是 lEOtcede。

大写漏判会错、顺序比错会乱，时间为什么是 O(n log n)

漏判大写元音是头一个坑：只写小写 a e i o u，会把 E、O、A 当辅音钉住不排，答案直接错，判元音时得把大写也算上。第二处是排序按字母表而不是 ASCII，E 和 e 一旦被当相等，输出顺序就乱。也有人排序时连辅音一起卷进去，或者回填时按收集顺序、从大到小取，这两种都会破坏「辅音不动、元音升序」的要求。复杂度上，两趟扫描各是 O(n)，中间给 k 个元音排序是 O(k log k)，k 最多等于 n，合起来时间 O(n log n)，篮子和结果串占 O(n) 空间。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def sortVowels(self, s: str) -> str:
        vs = [c for c in s if c.lower() in "aeiou"]
        vs.sort()
        cs = list(s)
        j = 0
        for i, c in enumerate(cs):
            if c.lower() in "aeiou":
                cs[i] = vs[j]
                j += 1
        return "".join(cs)

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    string sortVowels(string s) {
        string vs;
        for (auto c : s) {
            char d = tolower(c);
            if (d == 'a' || d == 'e' || d == 'i' || d == 'o' || d == 'u') {
                vs.push_back(c);
            }
        }
        sort(vs.begin(), vs.end());
        for (int i = 0, j = 0; i < s.size(); ++i) {
            char d = tolower(s[i]);
            if (d == 'a' || d == 'e' || d == 'i' || d == 'o' || d == 'u') {
                s[i] = vs[j++];
            }
        }
        return s;
    }
};

Java

import java.util.*;
class Solution {
    public String sortVowels(String s) {
        List<Character> vs = new ArrayList<>();
        char[] cs = s.toCharArray();
        for (char c : cs) {
            char d = Character.toLowerCase(c);
            if (d == 'a' || d == 'e' || d == 'i' || d == 'o' || d == 'u') {
                vs.add(c);
            }
        }
        Collections.sort(vs);
        for (int i = 0, j = 0; i < cs.length; ++i) {
            char d = Character.toLowerCase(cs[i]);
            if (d == 'a' || d == 'e' || d == 'i' || d == 'o' || d == 'u') {
                cs[i] = vs.get(j++);
            }
        }
        return String.valueOf(cs);
    }
}