Рассмотрим два способа решения:
1)При помощи сортировки:
1.1)Считаем введённые числа в массив и добавим в конец массива "минус бесконечность";
1.2)Отсортируем данный массив по не убыванию каким-нибудь эффективным алгоритмом (все одинаковые
элементы сгруппируются и "минус бесконечность встанет на нулевую позицию);
1.3)Ответом на вопрос будет количество значений переменной i на отрезке от 1 до N, таких что
A[i] != A[i+1].
2)При помощи множества:
2.1)Будем использовать какую-нибудь структуру, проверяющую наличие элемента не дольше чем за O(log N).
(например, set или сбалансированное дерево).
2.2)Последовательно будем считывать вводимые элементы и, если они ещё не присутствуют, то добавлять
их в структуру.
2.3)Ответом на вопрос будет количество элементов в структуре после считывания всех чисел.
Оба решения работают за O(N * log N).
Дано N чисел, требуется выяснить, сколько среди них различных.
Входные данные
В первой строке дано число N – количество чисел. (1 <= N <= 100000)
Во второй строке даны через пробел N чисел, каждое не превышает 2*109 по модулю.
Выходные данные
Выведите число, равное количеству различных чисел среди данных.