4765. Remove Duplicates from Sorted Array

Given a sorted array, remove the duplicates such that each element appears only once.

Input. The first line contains the size n (1 ≤ n ≤ 100) of array. The second line gives n integers in sorted order, each number is no greater than 100 by absolute value.

Output. Print the sorted array with removed duplicates.

Sample input 1	Sample output 1
9 -2 -2 0 1 1 2 4 4 5	-2 0 1 2 4 5
Sample input 2	Sample output 2
8 6 6 6 7 7 8 9 10	6 7 8 9 10

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 contains only one element – the first one: let i points to the end of resulting array, initially i = 0.

Let’s iterate in the variable j the array elements, starting from the second (j = 1, indexation starts from zero). If m[i] and m[j] are different, we must increase index i by 1 and assign m[i] = m[j]. Otherwise do nothing.

At the end of processing the cells m[0 .. i] contains the input sequence without duplicates.

Sample

Let’s simulate the second test case.

Algorithm realization

Declare the working array m.

int m[101];

Read the input array.

scanf("%d",&n);

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

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

Let initially the resulting array consists of only one element m[0] (i = 0). Iterate in the variable j the array elements, starting from the second (j = 1).

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

If m[i] and m[j] are different, increase index i by 1 and assign m[i] = m[j].

if (m[i] != m[j])

{

i++;

m[i] = m[j];

}

Print the resulting array without duplicates.

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

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

printf("\n");