Изменить массив так, чтобы все нули были перемещены в конец, сохраняя при этом порядок ненулевых элементов
Учитывая целочисленный массив nums, переместите все 0 в его конец, сохраняя относительный порядок ненулевых элементов.
Обратите внимание, что вы должны сделать это на месте, не копируя массив.
Пример 1:
Ввод: nums = [0,1,0,3,12] Вывод: [1,3,12,0,0] Пример 2:
Ввод: числа = [0] Вывод: [0]
Ограничения:
1 <= nums.length <= 104 -231 <= nums[i] <= 231 - 1
Мое решение: -
public class MoveZeros {
public void moveZeroes(int[] nums) {
List<Integer> li = new ArrayList<Integer>(nums.length);
for (int i = 0; i < nums.length; i++) {
if (nums[i] != 0) {
li.add(nums[i]);
}
}
while (nums.length > li.size()) {
li.add(0);
}
for (int i = 0; i < li.size(); i++)
nums[i] = li.get(i);
}
public static void main(String[] args) {
int num[] = { 0, 1, 0, 3, 12 };
MoveZeros move = new MoveZeros();
move.moveZeroes(num);
System.out.println(Arrays.toString(num));
}
}
Есть ли другой способ решить эту проблему?
Кроме того, этого решения нет. По вашим инструкциям вы не можете создать новый ArrayList и добавлять в него элементы.
Если вопрос связан с проблемой, у которой есть веб-страница, например веб-сайт практики программирования/конкурса, будет вежливо включить ссылку на эту страницу. Это правильная ссылка? leetcode.com/problems/move-zeroes/description
Вы можете сделать это на месте, изменив код пузырьковой сортировки. Но пузырьковая сортировка выполняется за O (n^2). В дальнейшем вас спросят, можете ли вы сделать это за меньшее время.
Есть множество способов. Вы можете отсортировать массив, используя стабильный алгоритм сортировки, позволяющий считать 0 большим, чем ненулевое, а все остальное — равным. Вы можете переместить ненулевое значение влево (что, в свою очередь, можно сделать несколькими способами) и заполнить нулями.
Ответы 2
Мы можем сделать это, не перемещая нули:
- Мы отслеживаем количество позиций, в которых у нас есть ненулевые элементы (используя
if (num != 0)). Одновременно мы перемещаем ненулевые элементы в начало массиваnums. - Затем мы устанавливаем все элементы после счетчика
posв ноль.
import java.util.Arrays;
public class MoveZeros {
public static void moveZeroes(int[] nums) {
if (nums == null || nums.length == 0)
return;
int pos = 0;
for (int num : nums) {
if (num != 0) {
nums[pos++] = num;
}
}
while (pos < nums.length) {
nums[pos++] = 0;
}
}
public static void main(String[] args) {
int[] nums = { 0, 1, 0, 3, 12 };
MoveZeros.moveZeroes(nums);
System.out.println(nums == null ? "null" : Arrays.toString(nums));
}
}
Принты
[1, 3, 12, 0, 0]
Комментарии:
- Кстати, статические методы следует вызывать с использованием имени класса, а не через экземпляр. – ВДЖС
Кстати, статические методы следует вызывать с использованием имени класса, а не через экземпляр.
Мы можем напрямую определить статический метод без необходимости. Имя экземпляра moveZeroes(nums); Спасибо
Вот мой метод для вашей справки.
Если элемент i массива равен 0, сдвиньте массив влево и поставьте 0 последним (вычислите --n, чтобы избежать повторной проверки 0). Если элемент i массива не равен 0, проверьте следующий, то есть i + 1.
public class MoveZeros {
public void moveZeroes(int[] nums) {
int i = 0, n = nums.length;
while(i < n)
if (nums[i] == 0) {
for (int j = i + 1; j < n; j++)
nums[j - 1] = nums[j];
nums[--n] = 0;
} else {
i++;
}
}
public static void main(String[] args) {
int num[] = { 0, 1, 0, 3, 12 };
MoveZeros move = new MoveZeros();
move.moveZeroes(num);
System.out.println(Arrays.toString(num));
}
}
Если ваше решение уже работает, возможно, вам повезет больше на codereview.stackexchange.com, но обязательно прочитайте их правила, прежде чем публиковать там сообщения.