Жребий Крижановского

В этой задаче нужно найти наименьшее число, которое встречается в данном массиве ровно один раз.

Первую группу ($$$n \le 10^3$$$) можно решить перебором всех элементов массива, посчитав количество появлений каждого элемента в массиве. Среди тех элементов, которые встречаются ровно один раз, требуется выбрать наименьший. Сложность такого решения $$$O(n^2)$$$.

[language=Python, frame=single]
n = int(input())
a = [int(input()) for i in range(n)]

ans = -1
for elem in a:
if a.count(elem) == 1:
if ans == -1 or elem < ans:
ans = elem
print(ans)

Во второй группе чисел может быть много, но все они не превосходят $$$10^5$$$. Для решения этой задачи воспользуемся идеей «подсчёта»: для каждого допустимого значения элемента массива подсчитаем, сколько раз оно встречается в исходном массиве. Для этого заведём массив cnt, в котором индекс $$$i$$$ принимает значение не превышающее $$$10^5$$$, и если мы считали число $$$num$$$, то увеличим на 1 значение cnt[$$$num$$$].

После этого в массиве cnt найдём такое минимальное значение индекса $$$i$$$, что cnt[$$$i$$$]$$$ = 1$$$. Если же подходящее значение не найдётся, то выведем $$$-1$$$.

[language=Python, frame=single]
n = int(input())
cnt = [0] * (10 ** 5 + 1)
for i in range(n):
num = int(input())
cnt[num] += 1

i = 0
while i < len(cnt) and cnt[i] != 1:
i += 1

if i < len(cnt):
print(i)
else:
print(-1)

Однако, если числа большие, то массив cnt не поместится в памяти. Чтобы такое решение проходило все тесты, нужно заменить массив cnt на структуру данных типа «словарь» (например, dict в Python или map в C++). Затем переберём ключи словаря в порядке возрастания и найти минимальный ключ, для которого значение в словаре будет равно 1.

[language=Python, frame=single]
n = int(input())
cnt = dict()
for i in range(n):
num = int(input())
if num not in cnt:
cnt[num] = 0
cnt[num] += 1
for num in sorted(cnt.keys()):
if cnt[num] == 1:
print(num)
break
else:
print(-1)

Есть и другое полное решение. Заметим, что если в массиве есть другой элемент, равный рассматриваемому, то после сортировки массива эти числа будут стоять рядом. А если число встречалось в массиве только один раз, то после сортировки соседями этого числа окажутся неравные ему числа. Отсортируем массив, пройдём по нему в порядке возрастания. Если текущий элемент не имеет равного соседа, то он и является ответом, так как если бы было меньшее число, удовлетворяющее условию, то мы бы уже нашли его. Если же мы прошли по всему массиву и не нашли ответ, то нужно вывести «-1»

[language=Python, frame=single]
n = int(input())
a = [int(input()) for i in range(n)]
a.sort()
a = [0] + a + [a[-1] + 1]
for i in range(1, n + 1):
if a[i - 1] < a[i] < a[i + 1]:
print(a[i])
break
else:
print(-1)

В этом варианте решения для удобства обработки мы добавили в массив два фиктивных элемента: 0 в начало и число, большее максимального элемента в массиве на 1 в конец для того, чтобы у первого и последнего элемента в массиве также были два соседа.