UniLecs #177. Distinct Array

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

Условие: для преобразования использовать только исходный массив.

Входные данные: arr - массив целых чисел, размер массива от 1 до 10^6.

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

Пример: arr = [1, 1, 2, 2, 2, 3]

Answer = [1, 2, 3]

Идея: так как по условию нам нельзя использовать вспомогательный массив, то результирующий массив будет записывать прямо в исходный. 

Для этого заведем отдельный счетчик i, который будем использовать для результирующего массива.

• Изначально "поместим" первый элемент в результирующий, т.е. i = 0.
• Далее в цикле перебираем элементы массива, начиная со 2го элемента (j = 1, индексация с нуля).
• Проверяем: если arr[i] != arr[j], то увеличиваем счетчик i на единицу и записываем новый элемент в i: arr[i] = arr[j]. Если элементы равны, то ничего не делаем.

После окончания цикла, мы сдвинем все уникальные элементы влево, а справа останутся дублирующие. Но в счетчике i хранится количество уникальных элементов.

Реализация:

https://gist.github.com/unilecs/a647883763a8eeb4af181ea0c9da42c9

Play-test: https://dotnetfiddle.net/m9gPFb