題目描述

題目鏈接

問題分析

這道體的思路非常簡單和好理解，找出字符串中的元音字符，然后按照ASSIC值進行排序，然后插入回對應的位置，解題步驟為：

1. 使用一個set（可以快速查找的容器），建立元音字符集合
2. 遍歷整個字符串s，挨個匹配是否在set中，然后使用一個數組記錄元音字符在字符串中的位置
3. 將s中的對應位置的元素提取出來，按照ASSIC進行排序
4. 挨個插入回字符串中

簡單模擬的解法

class Solution {set<char> s_set={'A','E','I','O','U','a','e','i','o','u'};
public:string sortVowels(string s) {string S(s);//遍歷字符串并查找元音字符的位置vector<int> v;for(int i=0;i<S.size();i++){if(s_set.find(S[i])!=s_set.end()){v.push_back(i);}}if(v.size()<=1) return s;        vector<int> v_copy(v);//提取元嬰字符，進行排序sort(v.begin(),v.end(),[S](int a,int b){return S[a] < S[b];});//插入回字符串中對應的位置string ret(s);for(int i=0;i<v.size();i++){ret[v_copy[i]] = s[v[i]];}return ret;}
};

這個代碼可以跑通大部分的測試用例2214 / 2216，但是在字符串超長的時候就會超時，所以需要進行優化

優化后

因為總共就10個元音字符（大小寫），可以使用一個數組或者map記錄每個字符在字符串中出現的次數。（數組的話就需要消耗58個單元，map需要消耗10個單元）

int v[58]={0};//根據ASSIC碼表的順序，ch-'A'
unordered_map<char,int> s_set={{'A',0},{'E',0},{'I',0},{'O',0},{'U',0},{'a',0},{'e',0},{'i',0},{'o',0},{'u',0}};

然后使用一個只讀的數組或者字符串，來設置好元音字符的順序,也就是待會插入元音字符的順序，根據ASSIC碼值

vector<char> sv = {'A','E','I','O','U','a','e','i','o','u'};

1. 挨個遍歷字符串s,統計出元音字符出現的次數（不能少），同時可以統計出現的位置（也可以不統計，在第4步直接從頭遍歷并判斷，統計是為了優化第四步的時間）
2. 對于排序元音字符，通過設置sv也已經做好
3. 使用一個index（作為一個雙指針），挨個遍歷到需要插入的元音字符（統計次數不為0）
4. 挨個遍歷到s中元音字符的位置，然后使用Index按順序插入元音字符

class Solution {unordered_map<char,int> s_set={{'A',0},{'E',0},{'I',0},{'O',0},{'U',0},{'a',0},{'e',0},{'i',0},{'o',0},{'u',0}};vector<char> sv = {'A','E','I','O','U','a','e','i','o','u'};
public:string sortVowels(string s) {vector<int> v;int i=0;for(auto& e: s){if(s_set.find(e)!=s_set.end()){s_set[e] +=1;v.push_back(i);}i++;}if(v.size()<=1) return s; int index = 0;for(auto& e:sv)//最多遍歷9次{if(s_set[e] > 0){break;}index++;}for(int i=0;i<v.size();i++){s[v[i]] = sv[index];s_set[sv[index]]--;while(index < sv.size()&&s_set[sv[index]]<=0){index++;}}return s;}
};

該問題，主要是需要優化不必要的耗時，思路并不難