题目描述
思路解析
一句话答案：LeetCode 2785 将字符串中的元音排序：辅音钉在原下标不动，只把元音抠出来按 ASCII 升序排好再依次回填，大写整体排在小写前，时间 O(n log n)、空间 O(n)。
把元音抠出来重排，辅音要放回哪里
给一个下标从 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) 空间。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢这套三步法:收集元音、单独排序、按序回填。辅音自始至终待在原地,我们只搬动元音。下面从收集元音开始,一格一格扫过去。
开工前 · 摆好舞台：先认一下画面。上面这排就是字符串 lEetcOde,一共 8 个字符。我用一个指针从左往右扫,紫色就是它当前站的位置。扫的时候把元音格子点亮成绿色、收进右边的元音篮子,辅音格子压成灰色留在原地。现在篮子还是空的,咱们从下标 0 开始。
扫描下标 0 · l(辅音,原地不动)：指针走到下标 0,这里是 l。它是辅音,不参与排序,直接把这一格压成灰色,记住它就钉在下标 0 这个位置,后面谁都不许挪它。指针继续往右。
扫描下标 1 · E(元音,收进篮子)：指针走到下标 1,这里是 E。它是元音,把它点亮成绿色,并且丢进元音篮子。这是收到的第 1 个元音,它的 ASCII 值是 69。别管它现在什么大小写,先原封不动收进来,排序留到第二步。
扫描下标 2 · e(元音,收进篮子)：指针走到下标 2,这里是 e。它是元音,把它点亮成绿色,并且丢进元音篮子。这是收到的第 2 个元音,它的 ASCII 值是 101。别管它现在什么大小写,先原封不动收进来,排序留到第二步。
扫描下标 3 · t(辅音,原地不动)：指针走到下标 3,这里是 t。它是辅音,不参与排序,直接把这一格压成灰色,记住它就钉在下标 3 这个位置,后面谁都不许挪它。指针继续往右。
扫描下标 4 · c(辅音,原地不动)：指针走到下标 4,这里是 c。它是辅音,不参与排序,直接把这一格压成灰色,记住它就钉在下标 4 这个位置,后面谁都不许挪它。指针继续往右。
扫描下标 5 · O(元音,收进篮子)：指针走到下标 5,这里是 O。它是元音,把它点亮成绿色,并且丢进元音篮子。这是收到的第 3 个元音,它的 ASCII 值是 79。别管它现在什么大小写,先原封不动收进来,排序留到第二步。
扫描下标 6 · d(辅音,原地不动)：指针走到下标 6,这里是 d。它是辅音,不参与排序,直接把这一格压成灰色,记住它就钉在下标 6 这个位置,后面谁都不许挪它。指针继续往右。
扫描下标 7 · e(元音,收进篮子)：指针走到下标 7,这里是 e。它是元音,把它点亮成绿色,并且丢进元音篮子。这是收到的第 4 个元音,它的 ASCII 值是 101。别管它现在什么大小写,先原封不动收进来,排序留到第二步。
收集完毕 · 看看篮子里的四个元音：一整趟扫完了。字符串里 4 个元音全进了篮子,按遇到的先后是 E e O e,ASCII 分别是 69、101、79、101。辅音 l t c d 已经乖乖钉在灰色位置上。接下来只对篮子里这四个元音动手,把它们按 ASCII 从小到大排好。
排序关键 · 大写 ASCII 小于小写：排序前先想清一件事:比的是 ASCII 值,不是字母表本身。大写字母 A 到 Z 的 ASCII 是 65 到 90,小写 a 到 z 是 97 到 122,所以任何大写字母的 ASCII 都小于任何小写字母。这里 E 是 69、O 是 79,都比小写 e 的 101 小。按 ASCII 从小到大,顺序就是 E、O、e、e,两个大写排在前面,两个小写 e 排在后面。
排好序 · 篮子变成 E O e e：排序完成。篮子里的元音现在按 ASCII 非递减排成了 E、O、e、e。你看,原来收集顺序是 E e O e,现在两个大写 E 和 O 被提到了前面,两个小写 e 落到后面。这就是第二步的成果,接下来第三步把它们按这个顺序依次填回元音位置。
第三步开始 · 再扫一遍按序回填：现在第三步,从下标 0 往右扫。规则很简单:碰到辅音,原样不动;碰到元音位置,就从排好序的篮子里从头开始,依次取出一个填进去。我用一个取用指针 j 指着篮子,现在 j 指着第 1 个元音 E。开始扫。
回填下标 0 · 保留辅音 l：指针到下标 0,这里是辅音 l。辅音不参与排序,原样保留,篮子的取用指针 j 一动不动。指针继续往右。
回填下标 1 · 填入元音 E：指针到下标 1,这是个元音位。从排好序的篮子里取出第 1 个元音 E,填到这一格。原来这里是 E,现在换成 E。取用指针 j 往后挪一格。
回填下标 2 · 填入元音 O：指针到下标 2,这是个元音位。从排好序的篮子里取出第 2 个元音 O,填到这一格。原来这里是 e,现在换成 O。取用指针 j 往后挪一格。
回填下标 3 · 保留辅音 t：指针到下标 3,这里是辅音 t。辅音不参与排序,原样保留,篮子的取用指针 j 一动不动。指针继续往右。
回填下标 4 · 保留辅音 c：指针到下标 4,这里是辅音 c。辅音不参与排序,原样保留,篮子的取用指针 j 一动不动。指针继续往右。
回填下标 5 · 填入元音 e：指针到下标 5,这是个元音位。从排好序的篮子里取出第 3 个元音 e,填到这一格。原来这里是 O,现在换成 e。取用指针 j 往后挪一格。
回填下标 6 · 保留辅音 d：指针到下标 6,这里是辅音 d。辅音不参与排序,原样保留,篮子的取用指针 j 一动不动。指针继续往右。
回填下标 7 · 填入元音 e：指针到下标 7,这是个元音位。从排好序的篮子里取出第 4 个元音 e,填到这一格。原来这里是 e,现在换成 e。取用指针 j 往后挪一格。
大功告成 · 答案 lEOtcede：扫完了。四个元音位从左到右依次填进了 E、O、e、e,辅音 l、t、c、d 始终待在原地没挪窝。最终字符串是 lEOtcede,和一开始说的对上了。回头看,大写 E 和 O 因为 ASCII 小,排到了前面的元音位,小写 e 落到了后面,辅音框架纹丝不动。
边界想清:无元音则原样返回;全小写元音重排成 aeiou;大写元音本就升序则不变。
面试重点:三步法收集排序回填、判元音转小写而排序用 ASCII、时间 O(n log n),元音只十种可用计数排序优化到 O(n)。
参考代码
from __future__ import annotationsfrom 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)复杂度
- 时间：O(n log n)，设字符串长度为 n,元音个数 k 不超过 n。两趟线性扫描各 O(n);中间对 k 个元音排序是 O(k log k),最坏 k 等于 n 就是 O(n log n)。排序这一步压过线性扫描,所以总时间 O(n log n)
- 空间：O(n)，按峰值算。元音篮子最多装 n 个字符,是 O(n);结果串也要 O(n)。排序本身的额外开销分语言:C plus plus 和 Java 通常是 O(log n) 的递归栈,Python 的 Timsort 最坏 O(n)。合起来空间是 O(n)
易错点
面试追问把动画讲成自己的话
追问这题的核心思路一句话怎么说?
追问大小写元音怎么统一处理?
追问复杂度是多少,能不能不排序?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
划分数组并满足最大差限制
LeetCode 2966 · 中等 · 沿着 贪心套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题