4760. Move
zeroes
Sequence of numbers is
given. Move all 0’s to the end of it while maintaining the relative order of
non-zero elements.
Input. First line contains
number of elements n (1 ≤ n ≤ 100) in the sequence. Second
line contains n integers, not greater
than 100 by absolute value.
Output. Print the sequence so
that all its 0’s are moved to the end, and the relative order of non-zero
elements is not changed.
|
Sample
input 1 |
Sample
output 1 |
|
6 3 0 5 0 0
-4 |
3 5 -4 0
0 0 |
|
|
|
|
Sample
input 2 |
Sample
output 2 |
|
7 0 0 -4 3
0 1 0 |
-4 3 1 0
0 0 0 |
SOLUTION
array
Algorithm analysis
Read the input sequence into array m. In the same array we will also build
the resulting array (so that not to allocate memory for another array of the
same length). Initially the resulting array is empty (let j contains the length of resulting array, initially j = 0). If the current value val of input sequence is not zero, put
it to the end of resulting array and increase the index j by 1: m[j++] = val. If val = 0, do nothing.
At the end of processing the cells m[0 .. j – 1] contain the input sequence without zeroes. Assign zeroes to
the cells m[j .. n – 1] and print the array m[0 .. n – 1].
Sample
Let’s simulate the second test case.
Algorithm realization
Declare the working array m.
int m[110];
Read the input sequence into array m.
scanf("%d",&n);
for(i = 0; i < n; i++)
scanf("%d",&m[i]);
Set up the initial length of resulting array to zero (j = 0). In the variable i
(0 ≤ i < n) iterate the indexes of sequence
elements. Move the nonzero elements m[i]
to the back of resulting array (m[j]
= m[i]) and increase its size by one
(j++).
for(j = i = 0; i < n; i++)
if (m[i] !=
0) m[j++] = m[i];
Fill the rest array elements till the (n
– 1)-th with zeroes.
while (j < n) m[j++] = 0;
Print the resulting sequence.
for(i = 0; i < n; i++)
printf("%d
",m[i]);
printf("\n");
Algorithm realization – sort
#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 realization – sort
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 realization – sort
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)