javascript - leetcode : render log files, 无法排序

Question

这是 discussion对于question .

我尝试将以下 C++ 答案(来自上面的讨论)转换为 javascript。

static bool myCompare(string a, string b){
        int i = a.find(' ');
        int j = b.find(' ');
        if(isdigit(a[i + 1]))
            if(isdigit(b[j + 1]))
                return false;       // a b are both digit logs, a == b, keep their original order
            else
                return false;       // a is digit log, b is letter log, a > b
        else
            if(isdigit(b[j + 1]))
                return true;        // a is letter log, b is digit log, a < b
            else {
                if (a.substr(i) == b.substr(j))
                    return a.substr(0,i) < b.substr(0,j); //If string part is the same, compare key
                else
                    return a.substr(i) < b.substr(j);   // a and b are both letter
            }
    }

    vector<string> reorderLogFiles(vector<string>& logs) {
        //The order of equal elements is guaranteed to be preserved in stable_sort.
        //Use sort() cannot pass the OJ. 
        stable_sort(logs.begin(), logs.end(), myCompare);
        return logs;
    }

我的解决方案如下:

var reorderLogFiles = function(logs) {
    return logs.sort(cmp);
}

var cmp = function(a, b) {
    let i = a.indexOf(' ');
    let j = b.indexOf(' ');

    if(isdigit(a[i + 1])) {
        if(isdigit(b[j + 1])) {
            // a, b digit, a == b
            return 0;
        } else {
            // a digit, b letter, b|a
            return 1;
        }
    } else {
        let condi;

        // a letter, b digit, a|b
        if(isdigit(b[j + 1])) {
            return -1;
        } else {
            // both letter
            if (a.substring(i+1) === b.substring(j+1)) {
                // start from space, all same, compare key
                condi = a.substring(0,i).localeCompare(b.substring(0,j));                
                //console.log('same', condi, a.substring(0,i), b.substring(0,j));

                return condi;
            } else {    
                condi = a.substring(i+1).localeCompare(b.substring(j+1));

                //console.log('not same', condi, a.substring(i+1), ' | ', b.substring(j+1));

                return condi;
            }
        }
    }

}

var isdigit = function(letter) {
    if(!isNaN(letter)) {
        return true;
    } else {
        return false;
    }
}

输入:

["6p tzwmh ige mc", "ns 566543603829", "ubd cujg j d yf", "ha6 1 938 376 5", "3yx 97 666 56 5", "d 84 34353 2249", "0 tllgmf qp znc", "s 1088746413789", "ys0 splqqxoflgx", "uhb rfrwt qzx r", "u lrvmdt ykmox", "ah4 4209164350", "rap 7729 8 125", "4 nivgc qo z i", "apx 814023338 8"]

我的输出:

["ubd cujg j d yf","u lrvmdt ykmox","4 nivgc qo z i","uhb rfrwt qzx r","ys0 splqqxoflgx","0 tllgmf qp znc","6p tzwmh ige mc","ns 566543603829","ha6 1 938 376 5","3yx 97 666 56 5","d 84 34353 2249","ah4 4209164350","rap 7729 8 125","apx 814023338 8","s 1088746413789"]

预期:

["ubd cujg j d yf","u lrvmdt ykmox","4 nivgc qo z i","uhb rfrwt qzx r","ys0 splqqxoflgx","0 tllgmf qp znc","6p tzwmh ige mc","ns 566543603829","ha6 1 938 376 5","3yx 97 666 56 5","d 84 34353 2249","s 1088746413789","ah4 4209164350","rap 7729 8 125","apx 814023338 8"]

我的输出与预期输出之间的差异:

“s 1088746413789”

Answer 1

你不能在javascript中通过传递0实现稳定排序，当有其他字符串被比较返回其他值而不是0。您必须将其索引存储在 map 中，然后进行相应的判断。我修改了你的代码如下:

var map = {};

var reorderLogFiles = function(logs) {
    logs.forEach(function(value,index){
        map[value] = index;
    });
    return logs.sort(cmp);
}

var cmp = function(a, b) {
    let i = a.trim().indexOf(' ');
    let j = b.trim().indexOf(' ');
    if(isDigit(a[i+1])){
        if(isDigit(b[j+1])) return map[a] - map[b];
        return 1;
    }

    if(isDigit(b[j+1])){
        return -1;
    }

    let cond = a.substring(i+1).localeCompare(b.substring(j+1));
    if(cond == 0) return a.substring(0,i).localeCompare(b.substring(0,j));
    return cond;
}

var isDigit = function(letter) {
    return !isNaN(letter);
}

• 首先，我们创建一个字符串映射及其出现索引。
• 稍后，我们用来决定什么时候a和b都是数字日志。
• 如果都是字母日志，则比较忽略标识符的日志。
• 在发生冲突时使用标识符。

您的代码存在如下问题:

// both letter
            if (a.substring(i+1) === b.substring(j+1)) {
                // start from space, all same, compare key
                condi = a.substring(0,i).localeCompare(b.substring(0,j));                
                //console.log('same', condi, a.substring(0,i), b.substring(0,j));

                return condi;
            } else {    
                condi = a.substring(i+1).localeCompare(b.substring(j+1));

                //console.log('not same', condi, a.substring(i+1), ' | ', b.substring(j+1));

                return condi;
            }

• 在这里，您正在比较忽略标识符的字母日志。但是假设两者相同(在平局的情况下)，您没有使用它们的标识符检查字典顺序。此外，首字母字符匹配也不适用于通常情况。

• 解决这个问题的最佳方法是将字母日志和数字日志收集在不同的数组中，然后只对字母日志进行排序，最后追加数字日志。如果许多日志是大量测试的数字日志，这将为您提供更好的平均案例性能。