Изначально программирование казалось мне самым сложным навыком на земле. Однако со временем это кажется более логичным, чем любое сложное жизненное обстоятельство. Отбросив философию, давайте рассмотрим проблему leetcode на основе бинарных файлов.
Проблема:
Учитывая массив nums, содержащий n различных чисел в диапазоне [0, n], вернуть единственное число в диапазоне, отсутствующее в массиве.
Интуиция
Перебрать значения от 0 до n
Подход
Я нашел длину чисел, а затем применил цикл for до значения длины чисел. Любое отсутствующее значение от 0 до n в массиве nums может быть возвращено
Сложность
- Временная сложность:
Как было предложено @Сайгин Аркан ранее, поскольку цикл перебирает n, следовательно, это решение имеет временную сложность O(n).
Ссылка: https://www.geeksforgeeks. org/анализ-алгоритмов-набор-4-анализ-циклов/ - Сложность пространства:
Так как мы не создаем никакой новой структуры данных. В каждый момент времени у нас есть одно целое число (из списка n), занимающее некоторое пространство, поэтому пространственная сложность будет O(1)
Ссылка: https://towardsdatascience.com/understanding-time-complexity-with-python- примеры-2bda6e8158a7
Код
class Solution:
def missingNumber(self, nums: List[int]) -> int:
n = len(nums)
for i in range(n+1):
if i not in nums:
return i
Приветствуются любые комментарии или предложения.
Следите за обновлениями
Удачного кодирования :)
