Демократія#356

Демократія (Розбір)

Президентом стає робот, чиє число унікальне (трапляється рівно один раз) і при цьому найменше серед усіх унікальних. Зверніть увагу, що просто найменше число не підходить: якщо воно трапилося двічі, воно вибуває, і треба дивитися далі.

Тому розв'язок такий:

  1. одним проходом порахуємо, скільки разів трапляється кожне число — зручно взяти словник або хеш-таблицю;

  2. серед чисел із лічильником рівно знайдемо найменше;

  3. якщо таких чисел немає взагалі, вибори не відбулися — виводимо ; інакше виводимо знайдене число.

Альтернативно можна відсортувати масив: тоді однакові числа стануть поруч, і достатньо знайти перший елемент, у якого і сусід зліва, і сусід справа відрізняються від нього.

Складність — зі словником або \mathcal{O}(N \log N) із сортуванням.