Наибольшее число как минимум в два раза больше других | Проблема LeetCode №1 | Python

В следующей серии я поделюсь решениями некоторых вопросов leetCode в Python. Сегодня мы решим Задачу №1.

Нахождение наибольшего числа как минимум в два раза больше других

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

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

Пример 1:

Input: nums = [3,6,1,0]
Output: 1
Explanation: 6 is the largest integer.
For every other number in the array x, 6 is at least twice as big as x.
The index of value 6 is 1, so we return 1.

Пример 2:

Input: nums = [1,2,3,4]
Output: -1
Explanation: 4 is less than twice the value of 3, so we return -1.

Пример 3:

Input: nums = [1]
Output: 0
Explanation: 1 is trivially at least twice the value as any other number because there are no other numbers.

Ограничения:

1 <= nums.length <= 50

0 <= nums[i] <= 100

Самый большой элемент в nums уникален.

Подход к решению этой проблемы:

Сначала нам нужно найти наибольшее число в массиве. Затем нам нужно проверить, является ли это наибольшее число в два раза больше каждого числа (кроме самого большого числа) в массиве. Если это не дважды, мы вернем -1.

Итак, чтобы проверить, является ли это число дважды другим, нам нужно пройти через весь массив, вычислить удвоение каждого числа и сравнить его с наибольшим числом. Если по какому-либо индексу удвоенное число не меньше наибольшего числа (т. е. наибольшее число не меньше удвоенного этого числа), то мы вернем -1. Если мы продолжим цикл и самое большое число будет как минимум в два раза больше любого другого числа в массиве, мы вернем это самое большое число.

Решение:

Временная сложность:

Временная сложность для этого алгоритма составляет O (n).

Ссылки:

Проблема с LeetCode:

Документация по Python: