Всем привет, сегодня мы будем решать задачу на LeetCode. Нам нужно наш массив кое как преобразовать. Нужно сделать код, который будет двигать элементы массива вправо на k шагов, а когда они дойдут до конца, переносить их в начало массива. Вы можете посмотреть это на примере:
Начинаем!!
Приступаем к обдумыванию задачки
Нужно подумать, как бы нам это реализовать. Нужно ли по шагам двигать каждый элемент или их можно сдвинуть сразу на k позиций?
Допустим, у нас есть массив длиной в 6 элементов и нужно сдвинуть их на 4 шага
Допустим, нам нужно сдвинуть элемент 4. Имея длину массива и число k, нужно вычислить его будущее положение в массиве.
Это можно сделать просто. Здесь понадобится операция, позволяющая получить остаток от деления "%".
4 имеет индекс 3. Считаем её будущее положение: (3 + k) % 6 = 1
Прибавляем к индексу (i) наш шаг (k) и делаем с ним "% 6", получаем в нашем случае 1, новый индекс.
Можно создать дополнительный массив, куда мы будем записывать результаты.
С дополнительным массивом всё будет намного легче и проще
Пишем код
Делаем!!
Создаём массив
Для начала заполним наш nums2 нулями, чтобы в дальнейшем проще было работать с индексами
Во время написания кода, я столкнулся с одним странным багом. У меня один и тот же результат, что бы я не выводил из функции. Как это исправить??
Даже так
Какой ужас...
У нас ещё одно ограничение, нам нужно менять nums на месте, мы не можем вывести новый массив через return.
Но мы можем сделать новый массив, в него аккуратненько положить числа, и оттуда по порядку залить их в старый массив
Да уж... Теперь понятно, почему так мало людей решило эту задачу. Условия немного странные...
Всё таки нужно быть внимательнее...
Я сделал три цикла: первый цикл создаёт второй массив и заполняет нулями, второй цикл вычисляет нужные индексы и заполняет их значениями, третий цикл заполняет первый массив элементами второго.
Повторю ещё раз. По условиям задачи ответ выводить можно только в nums. В этой задаче "return" не работает, ответ автоматически выводится в nums.
Запускаем...
На тренировочных двух значениях сработало.
Попробуем на более большом и хитром объёме данных.
Да! Задача решена!!
Но заметьте, производительность кода оставляет желать лучшего. Ну а теперь приступаем к самому сладкому - оптимизации!!!
Оптимизируем код
Первое, на что падает внимание, это три цикла. Нормально ли это? Должно ли так быть?
Мы можем убрать первый цикл вообще. В JavaScript можно заполнять элементы массива на любом индексе, даже если до этого индекса значений не было.
То есть так:
let mass = [];
mass[2] = 10
Результат: [empty, empty, 10]
Только вот наша производительность не считает, что это было хорошей идеей. Вместо того, чтобы вручную заполнить массив нулями и аккуратно их заменить, мы начали сразу устанавливать значения по индексу и оставили эту задачу нашему JavaScript. Наш JavaScript всё равно будет заполнять этот массив какими-то значениями перед вставкой значений, только он делает это своими механизмами, и программа выполняется ещё дольше...
Нет уж, спасибо. Нам такой "оптимизации" не надо.
Мы можем попробовать заранее высчитать "nums.length", записать его в переменную и не высчитывать его на каждом цикле
Это решение уже помогло нам ускорить программу.
Я думаю, а если сделать это по-другому? Если сделать так, чтобы в nums2 копировался массив nums, а потом из nums2 значения переносились обратно в nums по нужным индексам? Таким образом можно убрать первый цикл с нулями.
Вот таким образом мы избавились от лишнего цикла и оптимизировали процесс.
После запуска кода, код отрабатывает за 1 миллисекунду, что обгоняет 82,6% программистов по скорости.
Но стоит понимать, что время выполнения кода может меняться из раза в раз.
Запущу код несколько раз:
На LeetCode время выполнения кода нестабильно. Это может быть и 5ms, это может быть и 1ms и 2ms. Вот и думай, действительно ли ты оптимизировал код, или тебе так кажется...
Можно вынести переменную i, которая используется в двух циклах сразу за их пределы. Тогда не нужно будет дважды объявлять переменную и обращаться к памяти. На всякий случай я задал нашей переменной значение 0 при инициализации. Точно я не знаю, как это происходит, но лучше пусть наш JavaScript видит сразу, что это тип Number.
Скорость выполнения кода примерно такая же, зато сократился объём используемой памяти, и по нему наш код обогнал 79,1% программистов. Уже неплохо, код оптимизируется...
Но это до перезапуска. Наш LeetCode не особо стабилен.
Но всё же, объём памяти за все наши запуски так не сокращался.
...
Так, а что же я не заметил?? Эти два цикла можно же объединить. Я пытался сделать это в предыдущий раз, но тогда не было хороших условий для этого. Теперь же это реализуемо...
И да, я допустил ошибку. Элементы в пустой массив нужно вводить через push(), а не по индексам. Когда я редактировал код, я поменял его структуру и не заметил вот такую ошибку. Но код работает быстро, потому это элементы вводятся по порядку, а не начиная, например, с пятого индекса, в таком случае не всё так плохо.
Для начала сделаем так:
Код запускается за 1-2ms. (На LeetCode цифры постоянно меняются)
Но объединить эти два цикла в один не получится. В nums2 должен войти весь первоначальный nums, а он в этом цикле меняется. В nums одновременно записываются новые значения, и они записываются в nums2, чтобы снова записываться в nums. Ломается логика.
Ну что ж... Тогда оставляем наш код в таком виде
Подводим итоги
Получается, наш код выполняется за 1-4 ms. Но скорость и объём затрачиваемой памяти довольно хороши, наш код относительно оптимизирован. Но судя по статистике, двигаться есть куда, получается, есть ещё 17% разработчиков, которые смогли написать код лучше.
Эту задачу смогло решить мало людей, всего 44,6%. Это связано с тем, что задача не решается обычным способом, как остальные на LeetCode. Здесь нельзя выводить ответ через return, а надо менять саму "nums", об этом на английском написано в комментариях вверху над кодом. Здесь нужно быть внимательным и сообразительным, в первую очередь, ну а потом уже уметь решать задачи
Ну ладно, мы довольно хорошо провели время 😀. Ставьте лайки, пишите комментарии, и не забывайте подписываться на канал!! А я вас жду 😉