Find the Largest Number

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

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

Q: Почему текущее максимальное значение должно начинаться с первого элемента, а не с 0?

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

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

+10

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

Функция

findMax(nums: integer-array) → integer

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

Ограничения

1 ≤ nums.length ≤ 5000
-10⁹ ≤ nums[i] ≤ 10⁹

Примеры

Ввод: nums = [3, 17, 4, 12, 9]
Вывод: 17
Пояснение: Если читать слева направо, наибольшее значение на данный момент — 3, затем 17. Ни одно из значений 4, 12 или 9 не превышает 17, поэтому ответ — 17.

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

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

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

Можешь вернуть и наибольшее, и наименьшее значение примерно за 3n/2 сравнений вместо 2n, если сначала сравнивать значения парами?

Подсказки

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

Открыто 0 из 3

Решение

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

Отсортируйте копию и возьмите последнее значение

Идея

В списке, отсортированном от наименьшего значения к наибольшему, наибольшее значение находится в конце. Скопируй nums, чтобы список вызывающего кода остался прежним, отсортируй копию и верни её последний элемент. Для [3, 17, 4, 12, 9] отсортированная копия — это [3, 4, 9, 12, 17], а последний элемент — 17.

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

В JavaScript и TypeScript передай компаратор в sort. Без него числа сравниваются как текст, поэтому 12 и 17 оказываются перед 3.

Алгоритм

Скопируй nums.
Отсортируй копию от меньшего к большему, сравнивая числа как числа.
Верни последний элемент отсортированной копии.

def findMax(nums):
    ordered = sorted(nums)  # a sorted copy, smallest first
    return ordered[-1]

Один проход с текущим максимумом

Идея

Храни одно значение в переменной largest — наибольшее из тех, что встретились к этому моменту. Начни с nums[0], сравни его с каждым значением и заменяй всякий раз, когда встречается большее значение. Когда цикл завершится, largest будет сравнен с каждым элементом, поэтому ни один элемент списка не окажется больше него.

Для [3, 17, 4, 12, 9] переменная largest сначала равна 3, затем становится равной 17 и остается равной 17 при обработке 4, 12 и 9. Это n-1 полезных сравнений и одна дополнительная переменная.

Именно начальное значение nums[0] позволяет алгоритму работать со списками отрицательных чисел. Если вместо этого начать с 0, ни одно число в [-8, -3, -11, -3] не превзойдет его, поэтому ты вернешь 0 — значение, которого даже нет в списке.

Алгоритм

Присвойте largest значение nums[0].
Переберите все значения x в nums.
Если x > largest, присвойте largest значение x.
После цикла верните largest.

def findMax(nums):
    largest = nums[0]  # never 0: every value may be negative
    for x in nums:
        if x > largest:
            largest = x
    return largest

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

Цикл короткий, поэтому ошибки связаны с тем, где он начинается и что он читает.

Начинать largest с 0 или -1. Для любого списка, все значения которого меньше этого начального значения, возвращается число, которого нет в списке.
Начинать с выдуманного небольшого числа, например -1000000. Здесь значения доходят до -10^9, поэтому начальное значение всё равно окажется больше. Для nums[0] не нужно гадать.
Читать nums[0] в Lua или R, где первый элемент — nums[1]. Lua возвращает nil, а R — пустой вектор.
Выполнять цикл с условием i ≤ n в языке с индексацией с 0, из-за чего читается элемент за концом списка.
Сортировать без числового компаратора в JavaScript или TypeScript. В текстовом порядке [3, 17, 4, 12, 9] последним будет 9, поэтому вы вернёте 9 вместо 17.

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

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

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

Как найти наибольшее число в массиве, не используя max?

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

Почему текущее максимальное значение должно начинаться с первого элемента, а не с 0?

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

Когда сортировка — хороший способ найти наибольшее значение?

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

Python

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

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

Случай 1

Случай 2

Случай 3

Ввод

nums = [3, 17, 4, 12, 9]

Ожидается