2026-08-09按频率对元音排序。用go语言给定一个全部由小写英文字母构成的字符串你需要对其中的元音字母即 a、e、i、o、u进行重新排列而所有非元音字母保持原来的位置和顺序不变。排列的规则是首先统计每个元音字母在整个字符串中出现的次数次数越多的元音字母在结果中越靠前如果两个不同的元音字母出现次数相同则比较它们各自在原字符串中第一次出现的位置谁的位置更靠前谁就在排列结果中排在前面。最后输出经过这样处理的完整字符串。1 s.length 100000。s 由小写英文字母组成。输入 s “leetcode”。输出 “leetcedo”。解释字符串中的元音字母为 [‘e’, ‘e’, ‘o’, ‘e’]其出现频率为e 3o 1。按出现频率非递增排序后再放回原来的元音位置得到 “leetcedo”。题目来自力扣3913。解题过程详述建立元音识别机制构造一个长度为 123包含字符 ‘z’ 的 ASCII 码的整型数组mp将其所有元素初始化为 0。然后将字符a、e、i、o、u对应的数组位置分别标记为 1、2、3、4、5。这样后续在遍历字符串时只需将当前字符的mp值减去 1便能得到它在计数数组中的索引04。如果该字符不是元音mp值为 0则计算出的索引为 -1可据此快速过滤非元音字符。统计元音频率并记录首次出现顺序准备一个长度为 5 的整型数组cnt用于记录 a、e、i、o、u 各自出现的总次数初始均为 0。准备一个空的字节切片vowels用于按元音在字符串中第一次出现的顺序存放这些元音字母。从头到尾扫描原字符串s中的每一个字符ch通过mp[ch] - 1获取该字符的索引x如果x 0说明它不是元音直接跳过。检查cnt[x]是否为 0。若为 0表示这是该元音字母在字符串中第一次出现因此将ch追加到vowels切片尾部。将cnt[x]的值增加 1完成对该元音的一次计数。扫描结束后cnt中存储了每个元音的出现频率vowels切片中按首次出现位置保存了所有出现过的元音长度至多为 5。对元音按规则排序使用稳定排序算法对vowels切片进行排序排序的比较规则为取出两元音对应的出现次数次数大的排在前面。由于排序是稳定的当两个元音出现次数相同时它们在vowels切片中的原有相对顺序会被保留。而vowels切片的构建过程保证了它就是按各元音在原字符串中第一次出现的位置顺序排列的因此稳定排序后频率相同的元音会天然保持“首次出现位置越靠前越排在前面”的顺序。将排序结果重新放回字符串将原字符串s转换为可修改的字节切片t作为输出结果的骨架。初始化一个索引变量j 0指向vowels切片中当前正在使用的元音。再次从头遍历t的每一个字符位置i如果当前字符ch t[i]对应的mp[ch] 0说明该位置是非元音字母直接保留原字符不变继续下一个位置。如果mp[ch] ! 0说明该位置原本是元音需要进行替换。将t[i]改为vowels[j]也就是当前应使用的元音。找出被填入元音在计数数组中的索引x mp[t[i]] - 1然后将该元音的剩余次数cnt[x]减 1。如果cnt[x]减少后变为 0意味着这种元音已经被全部消耗完于是将j增加 1切换到vowels中的下一个元音供后续的元音位置使用。生成最终字符串将修改完毕的字节切片t转换为字符串并返回。此时所有非元音位置保持原样所有元音位置则按照要求频率非递增频率相同则按首次出现位置排序被重新排列后的元音填充。复杂度分析时间复杂度整个过程主要包含两次对字符串的完整遍历统计和替换每次遍历都只进行常数级别的操作数组访问、比较、赋值等因此时间复杂度为O(n)其中 n 为字符串的长度。对vowels切片进行排序的操作因其长度不超过 5可视为常数时间 O(1)。总时间复杂度为O(n)。额外空间复杂度算法中使用了长度为 5 的cnt数组、长度至多为 5 的vowels切片以及一个长度与原字符串相同的字节切片t。前三者的空间占用为 O(1)而t是为了构建修改后的字符串而从输入复制的一份副本其长度等于 n需要O(n)的额外空间。因此总的额外空间复杂度为O(n)。Go完整代码如下packagemainimport(fmtslices)varmp[z1]int{a:1,e:2,i:3,o:4,u:5}funcsortVowels(sstring)string{cnt:[5]int{}vowels:[]byte{}// 长度至多为 5for_,ch:ranges{x:mp[ch]-1ifx0{continue}ifcnt[x]0{vowelsappend(vowels,byte(ch))}cnt[x]}// 把 aeiou 按照出现次数从大到小排序slices.SortStableFunc(vowels,func(a,bbyte)int{returncnt[mp[b]-1]-cnt[mp[a]-1]})t:[]byte(s)j:0fori,ch:ranget{ifmp[ch]0{continue}t[i]vowels[j]x:mp[t[i]]-1cnt[x]--ifcnt[x]0{j// 消耗完了切换到下一种元音}}returnstring(t)}funcmain(){s:leetcoderesult:sortVowels(s)fmt.Println(result)}Python完整代码如下# -*-coding:utf-8-*-defsort_vowels(s:str)-str:# 元音到索引的映射 (a-0, e-1, i-2, o-3, u-4)vowel_to_idx{a:0,e:1,i:2,o:3,u:4}cnt[0]*5# 各元音出现次数vowels[]# 出现过的元音按首次出现顺序# 统计元音频率记录首次出现的元音顺序forchins:ifchinvowel_to_idx:idxvowel_to_idx[ch]ifcnt[idx]0:vowels.append(ch)cnt[idx]1# 稳定排序频率从大到小频率相同保持首次出现顺序vowels.sort(keylambdac:-cnt[vowel_to_idx[c]])# 替换元音位置reslist(s)j0fori,chinenumerate(res):ifchnotinvowel_to_idx:continue# 用当前排序中的元音替换res[i]vowels[j]idxvowel_to_idx[res[i]]cnt[idx]-1ifcnt[idx]0:j1return.join(res)if__name____main__:test_strleetcodeprint(sort_vowels(test_str))C完整代码如下#includeiostream#includestring#includevector#includealgorithm#includearraystd::stringsortVowels(conststd::strings){// 元音字符到索引的映射索引 0-4 分别对应 a, e, i, o, ustd::arrayint,26vowelIndex{};vowelIndex.fill(-1);vowelIndex[a-a]0;vowelIndex[e-a]1;vowelIndex[i-a]2;vowelIndex[o-a]3;vowelIndex[u-a]4;std::arrayint,5cnt{};// 各元音的出现次数std::vectorcharvowels;// 出现过的元音按首次出现顺序for(charch:s){intidx(chachz)?vowelIndex[ch-a]:-1;if(idx0)continue;// 非元音则跳过if(cnt[idx]0){vowels.push_back(ch);}cnt[idx];}// 稳定排序频率从大到小频率相同时保持首次出现的顺序std::stable_sort(vowels.begin(),vowels.end(),[](chara,charb){returncnt[vowelIndex[a-a]]cnt[vowelIndex[b-a]];});std::string ts;size_t j0;for(charch:t){intidx(chachz)?vowelIndex[ch-a]:-1;if(idx0)continue;// 非元音位置不变chvowels[j];intnewIdxvowelIndex[ch-a];cnt[newIdx]--;if(cnt[newIdx]0){j;// 当前元音消耗完毕切换下一个}}returnt;}intmain(){std::string sleetcode;std::string resultsortVowels(s);std::coutresultstd::endl;return0;}