4760. Сдвиг нулей

 

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

 

Вход. Первая строка содержит количество элементов n (1 ≤ n ≤ 100) в последовательности. Вторая строка содержит n целых чисел, по модулю не больших 100.

 

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

 

Пример входа 1

Пример выхода 1

6

3 0 5 0 0 -4

3 5 -4 0 0 0

 

 

Пример входа 2

Пример выхода 2

7

0 0 -4 3 0 1 0

-4 3 1 0 0 0 0

 

 

РЕШЕНИЕ

массивы

 

Анализ алгоритма

Читаем входную последовательность в массив m. В нем же будем строить и результирующий массив (чтобы не выделять память под еще один массив такой же длины). Изначально результирующий массив пуст (пусть j указывает на длину результирующего массива, изначально j = 0). Если очередное число val входной последовательности ненулевое, то положим его в конец результирующего массива и увеличим индекс j на 1: m[j++] = val. Если val = 0, то ничего не делаем.

По завершению обработки в ячейках m[0 .. j – 1] содержится входная последовательность без нулевых элементов. Занесем в ячейки m[j .. n – 1] нули и выведем весь массив m[0 .. n – 1].

 

Пример

Промоделируем второй тест.

 

Реализация алгоритма

Объявим рабочий массив m.

 

int m[110];

 

Читаем входную последовательность в массив m.

 

scanf("%d",&n);

for(i = 0; i < n; i++)

  scanf("%d",&m[i]);

 

Установим изначально длину результирующего массива равной нулю (j = 0). В переменной i (0 ≤ i < n) перебираем индексы элементов последовательности. Ненулевые элементы m[i] заносим в конец результирующего массива (m[j] = m[i]), увеличивая его размер на единицу (j++).

 

for(j = i = 0; i < n; i++)

  if (m[i] != 0) m[j++] = m[i];

 

Оставшиеся элементы массива вплоть до (n – 1)-го заполняем нулями.

 

while (j < n) m[j++] = 0;

 

Выводим результирующую последовательность.

 

for(i = 0; i < n; i++)

  printf("%d ",m[i]);

printf("\n");

 

Реализация алгоритма – сортировка

 

#include <cstdio>

#include <vector>

#include <algorithm>

using namespace std;

 

int n, i;

vector<int> v;

 

int f(int a, int b)

{

  if (a == 0 && b == 0) return 0;

  if (a == 0) return 0;

  if (b == 0) return 1;

  return 0;

}

 

int main(void)

{

  scanf("%d", &n);

  v.resize(n);

  for (i = 0; i < n; i++)

    scanf("%d", &v[i]);

 

  stable_sort(v.begin(), v.end(), f);

 

  for (i = 0; i < n; i++)

    printf("%d ", v[i]);

  printf("\n");

  return 0;

}

 

Java реализация – сортировка

 

import java.util.*;

 

public class Main

{

  public static class MyFun implements Comparator<Integer>

  {

    public int compare(Integer a, Integer b)

    {

      if (a == 0 && b == 0) return 0;

      if (a == 0) return 1;

      if (b == 0) return -1;

      return 0;

    }

  }

 

  public static void main(String[] args)

  {

    Scanner con = new Scanner(System.in);

    int n = con.nextInt();

    Integer m[] = new Integer[n];

    for(int i = 0; i < n; i++) m[i] = con.nextInt();

 

    Arrays.sort(m, new MyFun());

     

    for(int i = 0; i < n; i++) System.out.print(m[i] + " ");

    System.out.println();

    con.close();

  }

}

 

Python реализация – сортировка

 

from functools import cmp_to_key

 

def compare(a, b):

  if a == 0 and b == 0: return 0

  if a == 0: return 1

  if b == 0: return -1

  return 0

 

n = int(input())

lst = map(int, input().split())

res = sorted(lst, key = cmp_to_key(compare))

print(*res)