Leetcode: отображать файлы журнала, не в состоянии сортировать - PullRequest
Новая
       23

Leetcode: отображать файлы журнала, не в состоянии сортировать

0 голосов
/ 11 мая 2019

Вот обсуждение для вопроса .

Я попытался преобразовать следующие ответы на языке 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"

1 Ответ

0 голосов
/ 11 мая 2019

Вы не можете добиться стабильной сортировки в javascript, просто передав 0 , когда сравниваются другие строки с возвращением других значений, отличных от 0.Вы должны будете сохранить его индексы на карте, а затем судить соответственно.Я изменил ваш код, как показано ниже: 

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;
            }

  • Здесь вы сравниваете журналы писем, игнорируяидентификатор.Но допустим, что оба одинаковы (в ситуации связи), вы не проверяете лексикографическое упорядочение по их идентификаторам.Кроме того, сопоставление первых букв также не работает в обычном случае.

  • Лучший способ решить эту проблему - собрать буквенные и цифровые журналы в разныхмассивы, а затем сортировать только буквенные журналы и добавить цифры в конце.Это даст вам лучшую среднюю производительность по случаю, если многие журналы являются цифровыми журналами при большом количестве тестов.

...