Дан целочисленный массив nums. Необходимо переместить все нулевые элементы в конец массива, сохраняя относительный порядок элементов, не являющихся нулем. Решение должно производиться на месте, без использования дополнительного массива, а также должно иметь минимальную сложность по времени и пространству.
Пример:
Input: [0,1,0,3,12]
Output: [1,3,12,0,0]
public void moveZeroes(int[] nums) {
int index = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] != 0) {
nums[index++] = nums[i];
}
}
while (index < nums.length) {
nums[index++] = 0;
}
}
Описание алгоритма: Мы будем использовать два указателя: i и index. Сначала мы будем проходить по массиву nums с помощью указателя i и каждый раз, когда мы найдем ненулевой элемент, мы будем переносить его на место индекса index и увеличивать значение index. Затем мы заполняем оставшиеся позиции нулями. В результате все нули будут перемещены в конец массива, а все ненулевые элементы будут находиться в начале массива в том же порядке, что и в исходном массиве.
Данный алгоритм работает за линейное время O(n), где n - это длина массива nums.
1606 вопрос-ответ по Java: https://github.com/DEBAGanov/interview_questions
Tелеграмм канал: https://t.me/DEBAGanov
Мое резюме: https://github.com/DEBAGanov
