题面
你有一个日志数组 logs。每条日志都是以空格分隔的字串。
对于每条日志，其第一个字为字母数字标识符。然后，要么：
· 标识符后面的每个字将仅由小写字母组成，或；
· 标识符后面的每个字将仅由数字组成。
我们将这两种日志分别称为字母日志和数字日志。保证每个日志在其标识符后面至少有一个字。
将日志重新排序，使得所有字母日志都排在数字日志之前。字母日志按字母顺序排序，忽略标识符，标识符仅用于表示关系。数字日志应该按原来的顺序排列。
返回日志的最终顺序。
算法
算法一：
分成字母串和数字串，字母串排序，数字串接在尾部
算法二：
采用stable_sort，重载compare时：
1.当两个串均为数字串，返回false
2.一个数字串一个字母串，返回字母串较小
3.两个字母串，比较大小。
代码
算法一：
时间复杂度O(sum(length) * log(n))，额外空间复杂度O(sum(length))。
c++，8 ms
class Solution {
public:
static bool isnum(string s){
return (s[s.find(' ')+1]<='9'&&s[s.find(' ')+1]>='0');
}
static bool cmp(const string& s1,const string& s2){
return s1.substr(s1.find(' '))<s2.substr(s2.find(' '));
}
vector<string> reorderLogFiles(vector<string>& logs) {
vector<string>vnum,vletter;
for(auto i:logs)
if(isnum(i))
vnum.push_back(i);
else
vletter.push_back(i);
sort(vletter.begin(),vletter.end(),cmp);
vletter.insert(vletter.end(),vnum.begin(),vnum.end());
return vletter;
}
};
算法二：
时间复杂度O(sum(length) * log(n))，额外空间复杂度O(sum(length))。
c++，12 ms
class Solution {
public:
static bool isnum(string s){
return (s[s.find(' ')+1]<='9'&&s[s.find(' ')+1]>='0');
}
static bool cmp(const string& s1,const string& s2){
if(isnum(s1)&&isnum(s2))
return false;
if(isnum(s2))
return true;
if(isnum(s1))
return false;
return s1.substr(s1.find(' '))<s2.substr(s2.find(' '));
}
vector<string> reorderLogFiles(vector<string>& logs) {
stable_sort(logs.begin(),logs.end(),cmp);
return logs;
}
};
