937.重新排列日志文件

题目

思路

思路1：先遍历一边数组，分别将字母日志和数字日志存入vector<string>中，然后将字母日志使用自定义排序进行排序，再将数字日志加入排序后的字母日志即可。
思路2：直接使用 stable_sort进行自定义排序.

`stable_sort` 和 `sort` 的区别

sort是快速排序实现，因此是不稳定的；stable_sort是归并排序实现，因此是稳定的。（这里的稳定是指排序后相等元素的相对位置保持不变）
对于相等的元素sort可能改变顺序，stable_sort保证排序后相等的元素次序不变。
如果提供了比较函数，sort不要求比较函数的参数被限定为const，而stable_sort则要求参数被限定为const，否则编译不能通过。

class Solution {
public:
    vector<string> reorderLogFiles(vector<string>& logs) {
        vector<string> dig;  // 保存数字日志
        vector<string> let;  // 保存字母日志
        for(int i = 0; i < logs.size(); i++) {
            string str = logs[i];
            int j = 0;
            for(; j < str.size(); j ++){
                if(str[j] == ' ') break;
            }
            if(str[j + 1] >= '0' && str[j + 1] <= '9'){ //是数字日志
                dig.push_back(str);
            }
            else{ // 是字母日志
                let.push_back(str);
            }
        }
        sort(let.begin(), let.end(), [](string &a, string &b) {  //自定义sort排序
            int x = a.find(" ");
            int y = b.find(" ");
            string stra = a.substr(x + 1);
            string strb = b.substr(y + 1);
            if(stra != strb) return stra < strb;
            else return a < b;
        });
        for(int i = 0; i < dig.size(); i ++){
            let.push_back(dig[i]);
        }
        return let;
    }
};

时间复杂度：O(n \ log n)，其中 n 为 logs* 的字符数，是平均情况下内置排序的时间复杂度。
空间复杂度：O(n)，额外存放日志的数组

执行用时：16 ms, 在所有 C++ 提交中击败了23.57%的用户

内存消耗：12.4 MB, 在所有 C++ 提交中击败了31.52%的用户

通过测试用例：65 / 65

class Solution {
public:
    vector<string> reorderLogFiles(vector<string>& logs) {
        stable_sort(logs.begin(), logs.end(), [&](const string &a, const string &b){  // stable_sort
            int x = a.find_first_of(" "); // 找到a的第一个空格
            int y = b.find_first_of(" "); // 找到b的第一个空格
            bool isDigital_a = isdigit(a[x + 1]);
            bool isDigital_b = isdigit(b[y + 1]);
            if(isDigital_a && isDigital_b){  // 两个都是数字日志
                return false;
            }
            else if(!isDigital_a && !isDigital_b) { // 两个都是字母日志
                string stra = a.substr(x + 1);
                string strb = b.substr(y + 1);
                if(stra != strb) return stra < strb;
                else return a < b;
            }
            return isDigital_a ? false : true;  // 判断a是否是数字日志，若a是数字日志，则返回false
        });
        return logs;
    }
};

时间复杂度：O(n \ log n)，其中 n 为 logs* 的字符数，是平均情况下内置排序的时间复杂度。
空间复杂度：O(n)，额外存放日志的数组

执行用时：12 ms, 在所有 C++ 提交中击败了59.80%的用户

内存消耗：10.9 MB, 在所有 C++ 提交中击败了83.87%的用户

通过测试用例：65 / 65

题目

思路

stable_sort 和 sort 的区别

题解

`stable_sort` 和 `sort` 的区别