1. Идея

Нужно найти значение, которое встречается в массиве чаще всего. Если таких значений несколько, надо выбрать наименьшее.

Эталонное решение делает это через сортировку:

1. сортируем массив;
2. одинаковые элементы после сортировки стоят подряд;
3. проходим по массиву и считаем длину каждой группы одинаковых чисел;
4. запоминаем лучший ответ:
   • если текущая группа длиннее, чем лучшая раньше, обновляем ответ;
   • если длины равны, берём меньшее значение.

Такой подход хорошо подходит под ограничения задачи.

2. Наблюдения

Наблюдение 1

После сортировки все одинаковые элементы становятся соседними.

Например, массив

5 1 5 1 3

после сортировки превратится в

1 1 3 5 5

Теперь легко увидеть, сколько раз встречается каждое число:

• 1 — 2 раза
• 3 — 1 раз
• 5 — 2 раза

Максимальная частота равна 2, а среди чисел с такой частотой надо выбрать наименьшее, то есть 1.

Наблюдение 2

При проходе по отсортированному массиву достаточно хранить:

• current_value — какое число считаем сейчас;
• current_count — сколько раз подряд оно встретилось;
• best_value — лучший ответ на данный момент;
• best_count — его частота.

Наблюдение 3

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

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

3. Алгоритм

1. Считать n.
2. Считать массив a из n чисел.
3. Отсортировать массив.
4. Инициализировать:
   • best_value = a[0]
   • best_count = 1
   • current_value = a[0]
   • current_count = 1
5. Пройти по массиву с индекса 1 до n - 1:
   • если a[i] == current_value, увеличить current_count;
   • иначе:
     • сравнить текущую группу с лучшей:
       • если current_count > best_count, обновить лучший ответ;
       • если current_count == best_count и current_value < best_value, тоже обновить;
     • начать новую группу:
       • current_value = a[i]
       • current_count = 1
6. После цикла ещё раз сравнить последнюю группу с лучшей.
7. Вывести best_value.

4. Почему это работает

После сортировки каждый набор одинаковых значений образует один непрерывный отрезок.

При проходе по массиву алгоритм по очереди рассматривает все такие отрезки. Для каждого отрезка он точно знает:

• какое это число;
• сколько раз оно встретилось.

Значит, алгоритм проверяет все возможные кандидаты на ответ.

Дальше поддерживается инвариант: после обработки очередной завершённой группы в переменных best_value и best_count хранится правильный ответ среди всех уже рассмотренных групп:

• максимальная частота;
• при равной частоте — наименьшее значение.

Когда рассматривается новая группа:

• если она встречается чаще, чем лучший кандидат, нужно выбрать её;
• если она встречается столько же раз, но её значение меньше, тоже нужно выбрать её;
• иначе лучший кандидат не меняется.

После обработки всех групп, включая последнюю, в best_value будет именно то число, которое встречается чаще всего, а при равенстве частот — наименьшее из них.

5. Сложность

Сортировка массива из n элементов работает за O(n log n).

Последующий проход по массиву — за O(n).

Итоговая сложность:

• время: O(n log n)
• память: O(n) на хранение массива

6. Код на C++17

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;

    vector<long long> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    sort(a.begin(), a.end());

    long long best_value = a[0];
    int best_count = 1;

    long long current_value = a[0];
    int current_count = 1;

    for (int i = 1; i < n; i++) {
        if (a[i] == current_value) {
            current_count++;
        } else {
            if (current_count > best_count || (current_count == best_count && current_value < best_value)) {
                best_count = current_count;
                best_value = current_value;
            }
            current_value = a[i];
            current_count = 1;
        }
    }

    if (current_count > best_count || (current_count == best_count && current_value < best_value)) {
        best_count = current_count;
        best_value = current_value;
    }

    cout << best_value << "\n";
    return 0;
}

7. Код на Python 3

n = int(input())
a = list(map(int, input().split()))

a.sort()

best_value = a[0]
best_count = 1

current_value = a[0]
current_count = 1

for i in range(1, n):
    if a[i] == current_value:
        current_count += 1
    else:
        if current_count > best_count or (current_count == best_count and current_value < best_value):
            best_count = current_count
            best_value = current_value
        current_value = a[i]
        current_count = 1

if current_count > best_count or (current_count == best_count and current_value < best_value):
    best_count = current_count
    best_value = current_value

print(best_value)