4765. Удаление дублей из сортированного массива

Задан отсортированный массив целых чисел. Удалите из него дублирующие элементы так, чтобы каждое число в нем встречалось только один раз.

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

Выход. Выведите отсортированный массив с удаленными дублирующими элементами.

Пример входа 1	Пример выхода 1
9 -2 -2 0 1 1 2 4 4 5	-2 0 1 2 4 5
Пример входа 2	Пример выхода 2
8 6 6 6 7 7 8 9 10	6 7 8 9 10

РЕШЕНИЕ

массивы

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

Читаем входную последовательность в массив m. В нем же будем строить и результирующий массив (чтобы не выделять память под еще один массив такой же длины). Изначально результирующий массив содержит один элемент – первый: пусть i указывает на конец результирующего массива, изначально i = 0.

В переменной j перебираем элементы массива, начиная со второго (j = 1, индексация с нуля). Если m[i] и m[j] разные, то следует увеличить индекс i на 1 и присвоить m[i] = m[j]. Иначе ничего не делаем.

По завершению обработки в ячейках m[0 .. i] содержится входная последовательность без повторяющихся элементов.

Пример

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

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

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

int m[101];

Читаем входной массив.

scanf("%d",&n);

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

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

Пусть изначально результирующий массив состоит из единственного элемента m[0] (i = 0). В переменной j перебираем элементы массива, начиная со второго (j = 1).

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

Если m[i] и m[j] разные, то увеличиваем индекс i на 1 и присваиваем m[i] = m[j].

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

{

i++;

m[i] = m[j];

}

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

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

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

printf("\n");