题目描述
思路解析动画文字版
记牢这套三步法:收集元音、单独排序、按序回填。辅音自始至终待在原地,我们只搬动元音。下面从收集元音开始,一格一格扫过去。
开工前 · 摆好舞台：先认一下画面。上面这排就是字符串 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题