时间轴

2025-09-11

init

题目：

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
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