Второй наибольший элемент

Нахождение второго наибольшего элемента

Эта задача требует эффективного нахождения второго по величине элемента в списке. Важно понимать, что под "вторым наибольшим" может подразумеваться либо второй по значению (с учётом дубликатов), либо второй уникальный элемент. Рассмотрим оба подхода.

Простое решение: сортировка

def second_largest_simple(lst: list[int]) -> int | None:
    """
    Простое решение через сортировку.
    Временная сложность: O(n log n)
    """
    if len(lst) < 2:
        return None
    
    sorted_lst = sorted(lst, reverse=True)
    
    # Ищем второй уникальный элемент
    for i in range(1, len(sorted_lst)):
        if sorted_lst[i] < sorted_lst[0]:
            return sorted_lst[i]
    
    return None

# Тесты
print(second_largest_simple([1, 2, 3, 4, 5]))  # 4
print(second_largest_simple([5, 5, 4, 3]))      # 4
print(second_largest_simple([1, 1]))            # None

Оптимальное решение: один проход O(n)

Лучшее решение использует один проход через список, отслеживая максимум и второй максимум:

def second_largest(lst: list[int]) -> int | None:
    """
    Находит второй наибольший уникальный элемент за один проход.
    Временная сложность: O(n)
    Пространственная сложность: O(1)
    """
    if not lst or len(lst) < 2:
        return None
    
    max_val = float('-inf')
    second_max = float('-inf')
    
    for num in lst:
        if num > max_val:
            # Текущий максимум становится вторым
            second_max = max_val
            max_val = num
        elif num < max_val and num > second_max:
            # Текущее число больше второго максимума
            second_max = num
    
    # Если второй максимум не был инициализирован
    if second_max == float('-inf'):
        return None
    
    return second_max

# Тесты
print(second_largest([1, 2, 3, 4, 5]))  # 4
print(second_largest([5, 5, 4, 3]))      # 4
print(second_largest([1, 1]))            # None
print(second_largest([10, 20, 30]))      # 20
print(second_largest([-5, -1, -10]))     # -5

Решение через множество (уникальные элементы)

def second_largest_unique(lst: list[int]) -> int | None:
    """
    Находит второй наибольший элемент среди уникальных значений.
    Использует множество для удаления дубликатов.
    """
    if not lst:
        return None
    
    unique_nums = list(set(lst))
    
    if len(unique_nums) < 2:
        return None
    
    unique_nums.sort(reverse=True)
    return unique_nums[1]

# Тесты
print(second_largest_unique([5, 5, 4, 3]))  # 4
print(second_largest_unique([1, 1, 1]))      # None

Решение с использованием heap (приоритетная очередь)

import heapq

def second_largest_heap(lst: list[int]) -> int | None:
    """
    Использует heap для нахождения второго максимума.
    Временная сложность: O(n + k log n), где k = 2
    """
    if not lst or len(lst) < 2:
        return None
    
    # nlargest находит n наибольших элементов
    largest_two = heapq.nlargest(2, set(lst))  # Используем set для уникальности
    
    if len(largest_two) < 2:
        return None
    
    return largest_two[1]

# Тесты
print(second_largest_heap([1, 2, 3, 4, 5]))  # 4
print(second_largest_heap([5, 5, 4, 3]))      # 4
print(second_largest_heap([1, 1]))            # None

Рекурсивное решение

def second_largest_recursive(lst: list[int], index: int = 0, 
                            max_val: float = float('-inf'),
                            second_max: float = float('-inf')) -> int | None:
    """
    Рекурсивное решение.
    """
    if index == len(lst):
        if second_max == float('-inf'):
            return None
        return second_max
    
    num = lst[index]
    
    if num > max_val:
        second_max = max_val
        max_val = num
    elif num < max_val and num > second_max:
        second_max = num
    
    return second_largest_recursive(lst, index + 1, max_val, second_max)

# Тесты
print(second_largest_recursive([1, 2, 3, 4, 5]))  # 4
print(second_largest_recursive([5, 5, 4, 3]))      # 4
print(second_largest_recursive([1, 1]))            # None

Обработка граничных случаев

def second_largest_robust(lst: list[int]) -> int | None:
    """
    Устойчивое решение с полной обработкой граничных случаев.
    """
    # Проверка на пустой список
    if not lst:
        return None
    
    # Проверка на список с одним элементом
    if len(lst) == 1:
        return None
    
    # Получаем уникальные элементы
    unique_elements = list(set(lst))
    
    # Если меньше двух уникальных элементов
    if len(unique_elements) < 2:
        return None
    
    # Сортируем в порядке убывания
    unique_elements.sort(reverse=True)
    
    return unique_elements[1]

# Полные тесты
test_cases = [
    ([1, 2, 3, 4, 5], 4),
    ([5, 5, 4, 3], 4),
    ([1, 1], None),
    ([], None),
    ([42], None),
    ([10, 20], 10),
    ([-1, -2, -3], -2),
    ([100, 50, 100, 50, 75], 100),
]

for lst, expected in test_cases:
    result = second_largest_robust(lst)
    status = "✓" if result == expected else "✗"
    print(f"{status} second_largest({lst}) = {result} (expected {expected})")

Сравнение подходов

Рекомендация

Для большинства случаев используйте решение "один проход" (O(n) время, O(1) память):

def second_largest(lst: list[int]) -> int | None:
    """Оптимальное решение"""
    if not lst or len(lst) < 2:
        return None
    
    max_val = second_max = float('-inf')
    
    for num in lst:
        if num > max_val:
            second_max = max_val
            max_val = num
        elif num < max_val and num > second_max:
            second_max = num
    
    return second_max if second_max != float('-inf') else None

Это решение эффективно, элегантно и хорошо справляется со всеми граничными случаями.