题目描述

你有一个日志数组 logs。每条日志都是以空格分隔的字串。

对于每条日志，其第一个字为字母数字标识符。然后，要么：

• 标识符后面的每个字将仅由小写字母组成，或；
• 标识符后面的每个字将仅由数字组成。

我们将这两种日志分别称为字母日志和数字日志。保证每个日志在其标识符后面至少有一个字。

将日志重新排序，使得所有字母日志都排在数字日志之前。字母日志按字母顺序排序，忽略标识符，标识符仅用于表示关系。数字日志应该按原来的顺序排列。

返回日志的最终顺序。

样例

输入：["a1 9 2 3 1","g1 act car","zo4 4 7","ab1 off key dog","a8 act zoo"]
输出：["g1 act car","a8 act zoo","ab1 off key dog","a1 9 2 3 1","zo4 4 7"]

注意

• 0 <= logs.length <= 100
• 3 <= logs[i].length <= 100
• logs[i] 保证有一个标识符，并且标识符后面有一个字。

算法

(模拟) $O(n \log n)$

1. 没啥意义的模拟题，利用 STL 提供的 stable_sort，按照题目描述写好比较函数。
2. 比较函数首先区分两个字符串是哪种类型，然后对于两个都是字母日志的情况进一步比较字典序即可。

时间复杂度

• 排序的时间复杂度，为 $O(n \log n)$。

C++ 代码

bool cmp(const string &x, const string &y) {

    int type_x = false, type_y = false;
    int idx_x = -1, idx_y = -1;

    for (int i = 0; i < x.length(); i++)
        if (x[i] == ' ') {
            if (x[i + 1] >= '0' && x[i + 1] <= '9')
                type_x = true;
            idx_x = i + 1;
            break;
        }

    for (int i = 0; i < y.length(); i++)
        if (y[i] == ' ') {
            if (y[i + 1] >= '0' && y[i + 1] <= '9')
                type_y = true;
            idx_y = i + 1;
            break;
        }

    if (type_x == false && type_y == true)
        return true;
    else if (type_x == true)
        return false;

    string rx = x.substr(idx_x, x.length() - idx_x);
    string ry = y.substr(idx_y, y.length() - idx_y);

    if (rx != ry)
        return rx < ry;

    string tx = x.substr(0, idx_x);
    string ty = y.substr(0, idx_y);

    return tx < ty;
}

class Solution {
public:
    vector<string> reorderLogFiles(vector<string>& logs) {
        stable_sort(logs.begin(), logs.end(), cmp);
        return logs;
    }
};