Во время подготовки к техническим собеседованиям я столкнулся с проблемой, когда меня просили переместить определенные элементы в конец входного массива. Поскольку это проблема среднего уровня, я подумал, что создам запись в блоге о том, как я подошел к проблеме. Давайте начнем.

Подсказка

Учитывая массив целых чисел и целое число, создайте функцию, которая перемещает все экземпляры данного целого числа в конец массива. Затем верните измененный массив.

  • ** Примечание. Нет необходимости поддерживать порядок целых чисел в массиве.

Подход

То, как я подхожу к этому, похоже на многие другие проблемы со структурами данных и алгоритмами с указателями.

Сначала я создам две переменные для представления позиций массива: одну для начала, а другую для последней позиции массива.

Затем я могу создать условный оператор, который будет вызываться только тогда, когда два указателя не равны. Это означает, что указатель, начинающийся с первой позиции массива, будет перед указателем, начинающимся с конца массива.

Теперь для обработки крайнего случая ... что, если элемент во втором указателе (который начинается в конце массива) уже указывает на целое число, которое необходимо переместить в конец? В этом случае я просто уменьшу значение второго указателя и посмотрю на следующее число.

Затем, что делать, если элемент в первом указателе равен целому числу, которое мне нужно переместить в конец? Когда это произойдет, я могу поменять местами элементы по мере необходимости. Здесь я бы создал вспомогательную функцию для работы с функцией подкачки.

Затем, пока мы все еще находимся в области действия исходного условного оператора, увеличиваем первый указатель на единицу.

Наконец, верните модифицированный массив, и все будет хорошо. Теперь посмотрим на код.

Код

Функция примет два параметра: массив и целое число. Любой экземпляр целого числа необходимо переместить в конец.

Затем сделаем два указателя «i» и «j».

Теперь мы можем перейти к условной логике. Давайте использовать цикл while для вызова всякий раз, когда «i» меньше «j». Вне цикла while мы вызовем последний измененный массив. (Массив будет изменен в цикле while).

В цикле while я могу использовать больше условной логики. Во-первых, нам нужно позаботиться о граничном случае, когда элемент с индексом «j» может быть равен целому числу, которое нам нужно переместить в конец. Если да, то уменьшите «j».

Теперь, после второго цикла while, давайте воспользуемся оператором if для замены элементов, сюда же я включу желательный код для вспомогательного метода, который будет обрабатывать функциональность замены.

Теперь внутри начального цикла while и после двух внутренних циклов (второго цикла while и оператора if) увеличим указатель «i». Тогда приступим к вспомогательной функции.

Логика подкачки будет следующей:

  • создать временную переменную, которая будет содержать значение элемента с индексом «j»
  • в следующей строке элемент с индексом «j» будет установлен на элемент с индексом «i»
  • Затем в следующей строке элементу с индексом «i» будет присвоена временная переменная, которую мы изначально создали.

Посмотрим, как это выглядит.

Вот и все! Окончательный код должен выглядеть следующим образом:

Анализ сложности

временная сложность этого решения будет O (n) раз, где (n) - длина массива.

пространственная сложность этого решения - O (1), постоянная, пробел.