将字符串中的元音字母排序

标签: 字符串 排序

难度: Medium

给你一个下标从 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" 。

提示：

  • 1 <= s.length <= 105
  • s 只包含英语字母表中的 大写 和 小写 字母。

Submission

运行时间: 72 ms

内存: 17.4 MB

class Solution:
    def sortVowels(self, s: str) -> str:
        ans=list(s)
        n=len(ans)
        rem=[False]*n
        aei=set('aeiouAEIOU')
        col=[]
        for i in range(n):
            if ans[i] in aei:
                rem[i]=True
                col.append(ans[i])
        col.sort(key=lambda x:ord(x),reverse=True)
        for i in range(n):
            if rem[i]:
                ans[i]=col.pop()
        return ''.join(ans)

Explain

该题解的核心思路是首先创建一个与输入字符串 `s` 等长的列表 `ans`，用于存储最终结果。接着，使用一个布尔列表 `rem` 来标记每个位置的字符是否为元音字母。同时，创建一个集合 `aei` 存储所有元音字母的小写和大写形式，用于快速判断某个字符是否为元音。在遍历字符串 `s` 的过程中，如果发现元音字母，则在 `rem` 中相应位置标记为 `True`，并将该元音字母添加到列表 `col` 中。遍历完成后，对 `col` 进行排序，按照 ASCII 值逆序排序。最后，再次遍历字符串，根据 `rem` 中的标记，从 `col` 中取出排序后的元音字母填充到 `ans` 中的相应位置。最终通过 `join` 方法将列表 `ans` 转换为字符串形式返回。

时间复杂度: O(n + v log v)

空间复杂度: O(n)

class Solution:
    def sortVowels(self, s: str) -> str:
        ans = list(s) # 将字符串转换为列表，便于之后修改具体位置的字符
        n = len(ans) # 字符串的长度
        rem = [False] * n # 标记元音字母的位置
        aei = set('aeiouAEIOU') # 元音字母集合，支持快速查找
        col = [] # 存储所有元音字母
        for i in range(n):
            if ans[i] in aei: # 检查当前字符是否为元音
                rem[i] = True # 标记为元音位置
                col.append(ans[i]) # 收集元音字母
        col.sort(key=lambda x: ord(x), reverse=True) # 根据 ASCII 值逆序排序元音字母
        for i in range(n):
            if rem[i]: # 替换元音字母为排序后的元音
                ans[i] = col.pop() # 使用 pop() 从列表末尾取元音字母，这也符合逆序的排序结果
        return ''.join(ans) # 将列表转换回字符串并返回

Explore

使用布尔列表`rem`来标记元音位置的原因是为了避免在处理字符串`s`时进行复杂的字符替换操作。字符串在Python中是不可变的，因此直接修改字符串会导致每次修改都生成一个新的字符串对象，这样不仅效率低下，而且会增加额外的空间复杂度。通过使用布尔列表`rem`和另外一个列表`ans`来分别处理元音和辅音的位置，可以在`ans`中直接替换元音位置，这样处理更加高效且清晰。

这是题解中的一个错误。题目要求元音字母应该按照ASCII值的非递减顺序排列，即从小到大排序。在题解中，通过`reverse=True`实际上进行了逆序排序，这与题目要求相反。应该将`reverse=True`改为`reverse=False`或直接去除`reverse`参数，以实现正确的排序顺序。

使用`pop()`方法确实会从列表末尾取出元音字母，这本身不会影响到元音字母的顺序，因为在填充之前已经对元音字母进行了排序。然而，如果存在相同ASCII值的元音字母，使用`pop()`取出时会按照**后进先出**的顺序，这可能会导致相同ASCII值的元音字母在最终字符串中位置与原始输入相比发生变化。为保持相同ASCII值的元音字母的相对位置不变，应当从列表前端开始取元音字母填充，或者在排序时结合其原始位置信息进行稳定排序（即保证排序稳定性）。