leetcode每日一题 P2785 将字符串中的元音字母排序

---

时间轴

时间轴

2025-09-11

init

计数排序

---

题目：

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

https://leetcode.cn/problems/sort-vowels-in-a-string/description/?envType=daily-question&envId=2025-09-11

我采用先提取再排序，最后覆盖的方法，算法复杂度为 O(nlogn)

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

bool isVowel(char c)
{
        if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' || c == 'A' || c == 'E' ||
            c == 'I' || c == 'O' || c == 'U') {
                return true;
        }
        return false;
}
// 递增
int comparefunc(const void *a, const void *b)
{
        return *(char *)a - *(char *)b;
}
char *sortVowels(char *s)
{
        int len;
        int vowel_count = 0;
        char *str, *vowels;
        int index = 0;

        len = strlen(s);
        // 注意要复制len + 1个字节
        str = malloc((len + 1) * sizeof(char));
        strcpy(str, s);

        for (int i = 0; i < len; i++) {
                if (isVowel(str[i])) {
                        vowel_count++;
                }
        }
        vowels = (char *)malloc(vowel_count * sizeof(char));
        for (int i = 0; i < len && index < vowel_count; i++) {
                if (isVowel(str[i])) {
                        vowels[index] = str[i];
                        index++;
                }
        }
        qsort(vowels, vowel_count, sizeof(char), comparefunc);
        index = 0;
        for (int i = 0; i < len && index < vowel_count; i++) {
                if (isVowel(str[i])) {
                        str[i] = vowels[index];
                        index++;
                }
        }
        free(vowels);
        return str;
}

int main()
{
        // 常量字符串不可修改
        char *s = "lEetcOde";
        char *str;
        str = sortVowels(s);
        printf("%s\n", str);
        free(str);
}

推荐方法，利用计数排序的思想，即开辟一个将要排序的数的区间大小的数组，将要排序的数放入对应下标的数组元素中计数，然后累加和可以求得每个数前面有多少个数，从而直接确定这个数在排序后的数组中的位置，算法复杂度在 O(n)

ASCII码表

https://www.runoob.com/w3cnote/ascii.html

char *sortVowels(char *s)
{
        const char vowels[] = { 'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U' };
        int cnt[58];
        for (int i = 0; i < 58; i++) {
                cnt[i] = -1;
        }
        for (int i = 0; i < 10; i++) {
                int idx = vowels[i] - 'A';
                cnt[idx] = 0;
        }

        int len = strlen(s);
        for (int i = 0; i < len; i++) { // cnt数组中不为-1的即为元音字母
                int idx = s[i] - 'A';
                if (cnt[idx] != -1) {
                        cnt[idx]++;
                }
        }

        char *res = (char *)malloc(len + 1);
        strcpy(res, s);
        int idx = 0;
        for (int i = 0; i < len; i++) {
                int pos = res[i] - 'A';
                if (cnt[pos] != -1) { //如果是元音字母
                        while (cnt[idx] <= 0) {
                                idx++; //找到下一个元音字母
                        }
                        res[i] = idx + 'A';
                        cnt[idx]--;
                }
        }

        return res;
}

计数排序

https://www.runoob.com/w3cnote/counting-sort.html