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

这道题到底在问什么

输入

s = "lEetcOde"

输出

"lEOtcede"

输入

s = "lYmpH"

输出

"lYmpH"（没有元音，原样返回）

最优解：一步一步想明白

1. 3记牢这套三步法:收集元音、单独排序、按序回填。辅音自始至终待在原地,我们只搬动元音。下面从收集元音开始,一格一格扫过去。
2. 4先认一下画面。上面这排就是字符串 lEetcOde,一共 8 个字符。我用一个指针从左往右扫,紫色就是它当前站的位置。扫的时候把元音格子点亮成绿色、收进右边的元音篮子,辅音格子压成灰色留在原地。现在篮子还是空的,咱们从下标 0 开始。
3. 5指针走到下标 0,这里是 l。它是辅音,不参与排序,直接把这一格压成灰色,记住它就钉在下标 0 这个位置,后面谁都不许挪它。指针继续往右。
4. 6指针走到下标 1,这里是 E。它是元音,把它点亮成绿色,并且丢进元音篮子。这是收到的第 1 个元音,它的 ASCII 值是 69。别管它现在什么大小写,先原封不动收进来,排序留到第二步。
5. 7指针走到下标 2,这里是 e。它是元音,把它点亮成绿色,并且丢进元音篮子。这是收到的第 2 个元音,它的 ASCII 值是 101。别管它现在什么大小写,先原封不动收进来,排序留到第二步。
6. 8指针走到下标 3,这里是 t。它是辅音,不参与排序,直接把这一格压成灰色,记住它就钉在下标 3 这个位置,后面谁都不许挪它。指针继续往右。
7. 9指针走到下标 4,这里是 c。它是辅音,不参与排序,直接把这一格压成灰色,记住它就钉在下标 4 这个位置,后面谁都不许挪它。指针继续往右。
8. 10指针走到下标 5,这里是 O。它是元音,把它点亮成绿色,并且丢进元音篮子。这是收到的第 3 个元音,它的 ASCII 值是 79。别管它现在什么大小写,先原封不动收进来,排序留到第二步。
9. 11指针走到下标 6,这里是 d。它是辅音,不参与排序,直接把这一格压成灰色,记住它就钉在下标 6 这个位置,后面谁都不许挪它。指针继续往右。
10. 12指针走到下标 7,这里是 e。它是元音,把它点亮成绿色,并且丢进元音篮子。这是收到的第 4 个元音,它的 ASCII 值是 101。别管它现在什么大小写,先原封不动收进来,排序留到第二步。
11. 13一整趟扫完了。字符串里 4 个元音全进了篮子,按遇到的先后是 E e O e,ASCII 分别是 69、101、79、101。辅音 l t c d 已经乖乖钉在灰色位置上。接下来只对篮子里这四个元音动手,把它们按 ASCII 从小到大排好。
12. 14排序前先想清一件事:比的是 ASCII 值,不是字母表本身。大写字母 A 到 Z 的 ASCII 是 65 到 90,小写 a 到 z 是 97 到 122,所以任何大写字母的 ASCII 都小于任何小写字母。这里 E 是 69、O 是 79,都比小写 e 的 101 小。按 ASCII 从小到大,顺序就是 E、O、e、e,两个大写排在前面,两个小写 e 排在后面。
13. 15排序完成。篮子里的元音现在按 ASCII 非递减排成了 E、O、e、e。你看,原来收集顺序是 E e O e,现在两个大写 E 和 O 被提到了前面,两个小写 e 落到后面。这就是第二步的成果,接下来第三步把它们按这个顺序依次填回元音位置。
14. 16现在第三步,从下标 0 往右扫。规则很简单:碰到辅音,原样不动;碰到元音位置,就从排好序的篮子里从头开始,依次取出一个填进去。我用一个取用指针 j 指着篮子,现在 j 指着第 1 个元音 E。开始扫。
15. 17指针到下标 0,这里是辅音 l。辅音不参与排序,原样保留,篮子的取用指针 j 一动不动。指针继续往右。
16. 18指针到下标 1,这是个元音位。从排好序的篮子里取出第 1 个元音 E,填到这一格。原来这里是 E,现在换成 E。取用指针 j 往后挪一格。
17. 19指针到下标 2,这是个元音位。从排好序的篮子里取出第 2 个元音 O,填到这一格。原来这里是 e,现在换成 O。取用指针 j 往后挪一格。
18. 20指针到下标 3,这里是辅音 t。辅音不参与排序,原样保留,篮子的取用指针 j 一动不动。指针继续往右。
19. 21指针到下标 4,这里是辅音 c。辅音不参与排序,原样保留,篮子的取用指针 j 一动不动。指针继续往右。
20. 22指针到下标 5,这是个元音位。从排好序的篮子里取出第 3 个元音 e,填到这一格。原来这里是 O,现在换成 e。取用指针 j 往后挪一格。
21. 23指针到下标 6,这里是辅音 d。辅音不参与排序,原样保留,篮子的取用指针 j 一动不动。指针继续往右。
22. 24指针到下标 7,这是个元音位。从排好序的篮子里取出第 4 个元音 e,填到这一格。原来这里是 e,现在换成 e。取用指针 j 往后挪一格。
23. 25扫完了。四个元音位从左到右依次填进了 E、O、e、e,辅音 l、t、c、d 始终待在原地没挪窝。最终字符串是 lEOtcede,和一开始说的对上了。回头看,大写 E 和 O 因为 ASCII 小,排到了前面的元音位,小写 e 落到了后面,辅音框架纹丝不动。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

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)

#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;
    }
};

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);
    }
}

复杂度

面试官可能追问