Second Largest Number

Q: Какова временная сложность поиска второго по величине элемента?

Однопроходный и двухпроходный методы требуют времени O(n) и дополнительной памяти O(1) . Сначала выполнить сортировку — значит потратить время O(n log n) . Быстрее, чем за O(n) , справиться нельзя, потому что каждое значение нужно прочитать хотя бы один раз.

НовичокМассивы и строки

+10

Дан список целых чисел nums. Верните второе по величине уникальное значение: наибольшее значение, которое строго меньше максимального. Значения могут повторяться, поэтому для [5, 5, 3] ответ — 3, а не 5. В списке всегда есть как минимум два разных значения.

Функция

secondLargest(nums: integer-array) → integer

numsinteger-array: список целых чисел, содержащий как минимум два различных значения
Возвращаетinteger: наибольшее значение, которое меньше максимального

Ограничения

2 ≤ nums.length ≤ 5000
-10⁹ ≤ nums[i] ≤ 10⁹
nums содержит как минимум два различных значения.

Примеры

Ввод: nums = [4, 9, 2, 7, 9]
Вывод: 7
Пояснение: Максимум — это 9. Оно встречается дважды, но вторая копия максимума не учитывается, поэтому ответ — следующее по величине значение, 7.

Ввод: nums = [-5, -1, -8]
Вывод: -5
Пояснение: От наибольшего к наименьшему значения идут так: -1, -5, -8. Второе по величине — -5, хотя оно отрицательное.

Ввод: nums = [6, 6, 6, 3]
Вывод: 3
Пояснение: Существует только два различных значения: 6 и 3. Сколько бы раз ни повторялось 6, второе по величине значение — 3.

+15 скрытых тестов при отправке

Дополнительный вопрос

Можешь за один проход вернуть третье по величине уникальное значение, используя три переменные и не выполняя сортировку?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Есть две особенности, из-за которых эта задача сложнее поиска максимума. Максимум может повторяться, и повторное значение нельзя считать вторым по величине. Ответ может быть отрицательным, поэтому переменная, изначально равная 0, даст неверный ответ для списка, состоящего только из отрицательных чисел. Отслеживание двух наибольших различных значений за один проход с использованием строгих сравнений решает обе проблемы.

Отсортируйте и спуститесь ниже максимума

Идея

Отсортируй копию по возрастанию. Максимум находится в конце и может повторяться несколько раз подряд. Двигайся влево от конца, проходя все копии максимума; первое отличающееся значение — второе по величине. Для [6, 6, 6, 3] отсортированная копия выглядит так: [3, 6, 6, 6]: ты пропускаешь три 6 и доходишь до 3.

Вернуть предпоследний элемент — классическая ошибка в этом случае. Для [4, 9, 2, 7, 9] это вернёт 9, то есть снова максимум. При этом проход не может выйти за начало списка, потому что в списке есть как минимум два различных значения.

Ответ верный, но сортировка упорядочивает все значения, хотя тебя интересуют только два наибольших. Она требует O(n log n) времени, а копия — O(n) памяти.

Алгоритм

Скопируй nums и отсортируй копию от меньшего к большему.
Начни с индекса i, равного последней позиции.
Пока значение в позиции i равно максимальному, перемещай i на одну позицию влево.
Верни значение в позиции i.

def secondLargest(nums):
    ordered = sorted(nums)
    i = len(ordered) - 1
    # Step left past every copy of the maximum.
    while ordered[i] == ordered[-1]:
        i -= 1
    return ordered[i]

Два прохода

Идея

Раздели задачу на два прохода. В первом проходе найди максимум, как в задаче «Найти наибольшее число». Во втором проходе ищи наибольшее значение, которое строго меньше этого максимума. Для [4, 9, 2, 7, 9] первый проход находит 9, а второй пропускает обе 9 и сохраняет наибольшее из 4, 2 и 7, то есть 7.

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

Каждый проход находит текущий максимум, поэтому общая сложность составляет O(n) по времени и O(1) по памяти. Недостаток в том, что список приходится читать дважды, а это невозможно, если значения поступают по одному и исчезают после чтения.

Алгоритм

Один раз пройдись по nums и сохрани максимум в largest.
Установи second ниже любого допустимого значения.
Пройдись ещё раз. Для каждого x, для которого x < largest и x > second, установи second равным x.
Верни second.

def secondLargest(nums):
    largest = nums[0]
    for x in nums:
        if x > largest:
            largest = x
    second = float("-inf")  # below every allowed value
    for x in nums:
        if x < largest and x > second:
            second = x
    return second

Один проход с отслеживанием двух наибольших значений

Идея

Храните две переменные, largest и second, для двух наибольших различных значений, встреченных к этому моменту. Каждое новое значение x попадает в один из трёх случаев. Если x больше largest, старое значение largest становится вторым по величине, а x занимает первое место. Если x строго больше second и меньше largest, оно становится новым значением second. Во всех остальных случаях ничего не меняется.

Именно строгие сравнения позволяют обработать дубликаты. Для [4, 9, 2, 7, 9]: largest становится равным 4, затем 9, при этом second = 4. 2 ничего не меняет; 7 находится между 4 и 9, поэтому second = 7; последнее 9 равно largest, поэтому его пропускают. Ответ — 7.

Инициализируйте обе переменные значениями, меньшими любого возможного значения. Если начать обе переменные со значения 0, для [-5, -1, -8] результатом будет 0, поскольку ни одно значение не окажется больше 0. Поскольку список содержит два различных значения, в итоге second всегда будет содержать реальное значение из списка.

Алгоритм

Задай largest и second значения меньше любого допустимого значения.
Перебери все значения x в nums.
Если x > largest, присвой largest значение second, а largest присвой значение x.
Иначе, если x < largest и x > second, присвой second значение x.
После цикла верни second.

def secondLargest(nums):
    # Both start below every allowed value.
    largest = second = float("-inf")
    for x in nums:
        if x > largest:
            second = largest  # the old maximum drops to second place
            largest = x
        elif largest > x > second:
            second = x
    return second

Ловушки и крайние случаи

Большинство неверных ответов связано с повторяющимися максимальными значениями или отрицательными числами.

Возврат предпоследнего элемента отсортированного списка. Если максимум встречается несколько раз, как в [4, 9, 2, 7, 9], то предпоследний элемент тоже будет максимумом.
Инициализация переменных значением 0. В списке [-5, -1, -8] ни одно значение не больше 0, поэтому вы вернёте 0 — число, которого нет в списке.
Запись x >= largest в первом условии. Тогда вторая 9 переместит первую 9 в second, и вы вернёте 9.
Обновление second только при появлении нового максимума. В списке [10, 20, 15] значение 15 так и не попадёт в second, и вы вернёте 10.
Удаление повторов с помощью множества с последующей сортировкой. Это работает, но требует O(n) памяти и O(n log n) времени, хотя эту задачу можно решить за один проход.

Частые вопросы4

Как найти второе по величине число в массиве за один проход?

Храните наибольшее и второе по величине отличающиеся значения, встреченные к этому моменту. Когда значение превышает наибольшее, прежнее наибольшее становится вторым. Когда значение находится строго между ними, оно заменяет второе. После одного прохода во второй переменной будет ответ.

Какова временная сложность поиска второго по величине элемента?

Однопроходный и двухпроходный методы требуют времени O(n) и дополнительной памяти O(1). Сначала выполнить сортировку — значит потратить время O(n log n). Быстрее, чем за O(n), справиться нельзя, потому что каждое значение нужно прочитать хотя бы один раз.

Как дубликаты влияют на поиск второго по величине элемента?

В этой задаче нужно найти второе по величине уникальное значение, поэтому повторения максимума пропускаются. Для [9, 9, 7] ответ — 7. В некоторых версиях задачи вместо этого считают позиции и ответом будет 9, поэтому перед тем, как писать код, проверь, что имеется в виду.

Что следует вернуть, если второго по величине значения нет?

Здесь это невозможно: список всегда содержит два различных значения. В общем случае для списка вроде [4, 4, 4] ответа нет, и нужно вернуть маркер, например -1 или null, либо вызвать ошибку. Можно обнаружить этот случай, если после цикла second всё ещё содержит исходное значение.

Python

def secondLargest(nums):
    # Напишите код здесь

Тестовые случаи

Случай 1

Случай 2

Случай 3

Ввод

nums = [4, 9, 2, 7, 9]

Ожидается

Second Largest Number

Функция

Ограничения

Примеры

Подсказки

Решение

Отсортируйте и спуститесь ниже максимума

Два прохода

Один проход с отслеживанием двух наибольших значений

Ловушки и крайние случаи

Частые вопросы4

Похожие задачи