Решение задачи сортировка людей в парке по росту

170

07 октября 2021, 04:40

Вчера на сайте codesignal решал интересное задание сортировка людей по их росту в парке не трогая деревья.

В парке есть люди разного роста и деревья задача отсортировать людей не трогая деревья.

Вход дается массив такого рода [-1, 150, 190, 170, -1, -1, 160, 180] на выходе надо получить такой массив [-1, 150, 160, 170, -1, -1, 180, 190].

-1 (деревья) не трогаем остальное сортируем.

Я сделал данную задачу может и криво но вопрос не в этом.Вопрос в том что лучший ответ был следующий

const arr = [-1, 150, 190, 170, -1, -1, 160, 180]; 
 
function sortByHeight(a) { 
    var s = a.filter(h => h > 0).sort((a, b) => a - b); 
    console.log(s); 
    return a.map(p => { 
        if (p !== -1) { 
            return s.shift(); 
        } 
        return -1; 
    }) 
}  
console.log(sortByHeight(arr)); // [-1, 150, 160, 170, -1, -1, 180, 190]

И мне очень трудно понять его работу.

То есть почему если написать console.log(s) после вот этой строки var s = a.filter(h => h > 0).sort((a, b) => a - b) мне показывает пустой массив ?

Там же должно быть что то вроде вот такого массива

[150, 160, 170, 180, 190]

Почему он удаляет первый элемент пустого массива вот тут return s.shift();? Надо чтобы кто нибудь объяснил работу этого кода полностью.Спасибо заранее.

Answer 1

Разбор кода по порядку. Первая строка

var s = a.filter(h => h > 0).sort((a, b) => a - b);

Метод filter отсеивает все элементы, которые меньше 0, в нашем случае это деревья

[-1, 150, 190, 170, -1, -1, 160, 180] ==> [150, 190, 170, 160, 180]

Метод sort, соответственно, сортирует. Стрелочная функция, переданная в sort должна возвращать отрицательное число, если левый меньше правого, положительное, если больше, и ноль, если они равны. a - b подходит.

[150, 190, 170, 160, 180] ==> [150, 160, 170, 180, 190]

Следующее выражение

return a.map(p => {
    if (p !== -1) {
        return s.shift();
    }
    return -1;
})

Метод map итеративно применяет переданную в него функцию к элементам массива. При этом проход осуществляется именно по исходному массиву a, заметьте.

Метод shift как бы "вырезает" первый элемент массива, "сдвигая" весь массив на 1 элемент влево (отсюда и название shift). При этом вырезанный элемент возвращается методом.

В функции если текущий элемент p не является деревом (не равен -1), то вместо него возвращается первый элемент отсортированного массива s.

Так как массив s уже отсортирован, первый его элемент будет всегда наименьшим, благодаря чему можно по порядку брать элементы из начала массива s с помощью shift и получить отсортированный массив снова.

Вот наглядный пример работы этого алгоритма:

1: [-1, 150, 190, 170, -1, -1, 160, 180]
     ^
2: [-1, 150, 190, 170, -1, -1, 160, 180] <== [150, 160, 170, 180, 190]
         ^                                     ^
3: [-1, 150, 190, 170, -1, -1, 160, 180] <== [160, 170, 180, 190]
              ^                                ^
4: [-1, 150, 160, 170, -1, -1, 160, 180] <== [170, 180, 190]
                   ^                           ^
5: [-1, 150, 190, 170, -1, -1, 160, 180]
                        ^
6: [-1, 150, 190, 170, -1, -1, 160, 180]
                            ^
7: [-1, 150, 160, 170, -1, -1, 160, 180] <== [180, 190]
                                ^              ^
8: [-1, 150, 160, 170, -1, -1, 180, 180] <== [190]
                                     ^         ^
РЕЗУЛЬТАТ: [-1, 150, 160, 170, -1, -1, 180, 190]