Во время подготовки к техническим собеседованиям я столкнулся с проблемой, когда меня просили переместить определенные элементы в конец входного массива. Поскольку это проблема среднего уровня, я подумал, что создам запись в блоге о том, как я подошел к проблеме. Давайте начнем.
Подсказка
Учитывая массив целых чисел и целое число, создайте функцию, которая перемещает все экземпляры данного целого числа в конец массива. Затем верните измененный массив.
- ** Примечание. Нет необходимости поддерживать порядок целых чисел в массиве.
Подход
То, как я подхожу к этому, похоже на многие другие проблемы со структурами данных и алгоритмами с указателями.
Сначала я создам две переменные для представления позиций массива: одну для начала, а другую для последней позиции массива.
Затем я могу создать условный оператор, который будет вызываться только тогда, когда два указателя не равны. Это означает, что указатель, начинающийся с первой позиции массива, будет перед указателем, начинающимся с конца массива.
Теперь для обработки крайнего случая ... что, если элемент во втором указателе (который начинается в конце массива) уже указывает на целое число, которое необходимо переместить в конец? В этом случае я просто уменьшу значение второго указателя и посмотрю на следующее число.
Затем, что делать, если элемент в первом указателе равен целому числу, которое мне нужно переместить в конец? Когда это произойдет, я могу поменять местами элементы по мере необходимости. Здесь я бы создал вспомогательную функцию для работы с функцией подкачки.
Затем, пока мы все еще находимся в области действия исходного условного оператора, увеличиваем первый указатель на единицу.
Наконец, верните модифицированный массив, и все будет хорошо. Теперь посмотрим на код.
Код
Функция примет два параметра: массив и целое число. Любой экземпляр целого числа необходимо переместить в конец.
Затем сделаем два указателя «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), постоянная, пробел.