Найти два наибольших числа: алгоритм и примеры

Суть задачи

Найти два наибольших числа — значит определить максимальное значение в наборе данных и следующее за ним по величине. Задача встречается в программировании (обработка массивов и списков), в математике (сравнение нескольких чисел) и в повседневных расчётах — например, при выборе двух лучших результатов из таблицы.

Есть два принципиально разных подхода:

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

Первый способ быстрее и эффективнее, второй — проще для понимания и подходит для небольших наборов данных.

Алгоритм без сортировки

Идея в том, чтобы завести две переменные — max1 (наибольшее число) и max2 (второе по величине) — и обновлять их по ходу перебора чисел.

Шаги алгоритма:

1. Присвоить max1 и max2 минимально возможное значение (или взять первые два числа набора).
2. Взять очередное число из списка.
3. Если оно больше max1 — сдвинуть текущий max1 в max2, а новое число записать в max1.
4. Иначе, если оно больше max2, но меньше max1 — записать его в max2.
5. Повторять для всех оставшихся чисел.
6. По завершении перебора max1 и max2 содержат искомую пару.

Такой алгоритм требует ровно одного прохода по данным и не создаёт дополнительных копий массива, поэтому подходит для больших объёмов данных.

Пример пошагового разбора

Дан набор чисел: 5, 1, 12, 12, 8, 3.

Результат: наибольшее число — 12, второе по величине — тоже 12, поскольку в наборе есть повтор. Если нужна пара из разных значений, повторяющиеся элементы при сравнении пропускают.

Реализация на Python

def two_largest(numbers):
    max1 = max2 = float('-inf')
    for n in numbers:
        if n > max1:
            max1, max2 = n, max1
        elif n > max2:
            max2 = n
    return max1, max2

a = [2, 2, 3, -15, 2, -7, -12, 2, 3]
print(two_largest(a))  # (3, 3)

Если нужны именно два разных числа (без учёта дублей), условие меняют так, чтобы max2 обновлялся только при n != max1:

def two_largest_distinct(numbers):
    max1 = max2 = float('-inf')
    for n in numbers:
        if n > max1:
            max1, max2 = n, max1
        elif max1 > n > max2:
            max2 = n
    return max1, max2

Компактный вариант через встроенную функцию max() тоже возможен, но требует двух проходов и хуже читается на больших данных:

a = [2, 2, 3, -15, 2, -7, -12, 2, 3]
m1 = max(a)
m2 = max(x for x in a if x != m1)
print(m1, m2)

Реализация на псевдокоде и других языках

Логика одинакова для любого языка программирования — меняется только синтаксис.

Псевдокод:

max1 = -infinity
max2 = -infinity
для каждого x в списке:
    если x > max1:
        max2 = max1
        max1 = x
    иначе если x > max2:
        max2 = x
вернуть max1, max2

На C# та же идея реализуется без сортировки и без создания дополнительного массива:

int max1 = int.MinValue, max2 = int.MinValue;
foreach (int x in arr) {
    if (x > max1) {
        max2 = max1;
        max1 = x;
    } else if (x > max2) {
        max2 = x;
    }
}

Способ через сортировку

Если массив небольшой или производительность не критична, проще отсортировать данные и взять два последних элемента:

a = [2, 2, 3, -15, 2, -7, -12, 2, 3]
a_sorted = sorted(a)
print(a_sorted[-1], a_sorted[-2])  # 3 3

Сортировка занимает больше времени на больших наборах данных (порядка n·log n операций против n при линейном проходе), но код получается короче и нагляднее — это удобно для учебных задач и разовых расчётов.

Особые случаи

• Массив из одного элемента. Второго максимума не существует — функция должна возвращать об этом явный сигнал, а не подставлять произвольное число.
• Все элементы равны. Оба максимума окажутся равны этому числу — это корректный результат, если задача не требует уникальности значений.
• Отрицательные числа. Инициализировать переменные максимума нужно значением «минус бесконечность» (или первыми элементами набора), а не нулём — иначе отрицательные числа могут быть проигнорированы.
• Три и меньше чисел. Для трёх чисел проще сравнить их попарно: сначала найти большее из первых двух, затем сравнить результат с третьим — второе по величине число останется после исключения крайних значений.

Частые ошибки

• Инициализация переменных максимума нулём — при работе с отрицательными числами это даёт неверный результат.
• Использование max() дважды внутри цикла — резко замедляет вычисления на больших списках, так как каждый вызов заново обходит весь набор данных.
• Путаница между «вторым наибольшим уникальным значением» и «вторым элементом после сортировки» — если в наборе есть повторы, эти два понятия дают разные ответы.
• Отсутствие проверки на длину массива — при менее чем двух элементах алгоритм должен явно сообщать об невозможности найти пару, а не возвращать случайное значение.