Выберите наилучший вариант для решения поставленной задачи:
Входные данные: nums = [4,3,2,7,8,2,3,1]
– Выходные данные: [5,6]
Пример исходного кода:
//—————————————
def find_missing_numbers(nums, min_number, max_number):
missing_numbers = []
…
return missing_numbers
nums = [4,3,2,7,8,2,3,1]
print(find_missing_numbers(nums, 1, 8))
//—————————————
В примере выше ответ будет [5, 6]”
python
def find_missing_numbers(nums, min_number, max_number):
missing_numbers = []
# Сортируем список в порядке возрастания
nums.sort()
# Переменная для отслеживания предыдущего числа
prev_num = min_number
# Проверяем каждое число в отсортированном списке
for num in nums:
if num > prev_num:
# Если предыдущее число меньше текущего,
# то пропущено как минимум одно число,
# добавляем все пропущенные числа в промежутке (prev_num, num-1) в список пропущенных чисел
for missing_num in range(prev_num, num):
missing_numbers.append(missing_num)
# Обновляем значение предыдущего числа
prev_num = num + 1
# Проверяем, есть ли пропущенные числа после последнего числа в списке
if prev_num <= max_number:
for missing_num in range(prev_num, max_number + 1):
missing_numbers.append(missing_num)
return missing_numbers
nums = [4,3,2,7,8,2,3,1]
print(find_missing_numbers(nums, 1, 8))
Данный подход имеет сложность O(nlogn), где n - количество элементов в списке nums, так как сначала мы выполняем сортировку, которая имеет сложность O(nlogn), а затем выполняем один проход по отсортированному списку.
2. **Использование хэш-таблицы**:
Идея состоит в том, чтобы использовать хэш-таблицу для отметки всех чисел в списке nums. Затем мы можем пройтись по всем числам в заданном диапазоне [min_number, max_number] и проверить, какие числа отсутствуют в хэш-таблице.
Исходный код решения:
python
def find_missing_numbers(nums, min_number, max_number):
missing_numbers = []
# Создаем хэш-таблицу для отметки чисел в списке
num_set = set(nums)
# Проверяем каждое число в заданном диапазоне
for num in range(min_number, max_number+1):
if num not in num_set:
missing_numbers.append(num)
return missing_numbers
nums = [4,3,2,7,8,2,3,1]
print(find_missing_numbers(nums, 1, 8))
Этот подход имеет сложность O(n), где n - разность между максимальным и минимальным числом в заданном диапазоне, так как мы выполняем только один проход по числам в заданном диапазоне.
Оба подхода правильно решают поставленную задачу. Выбор подхода зависит от контекста и требований к производительности. Если список nums уже отсортирован, и его порядок играет роль, то первый подход может быть предпочтительным. В противном случае, если требуется оптимальная производительность, то второй подход с использованием хэш-таблицы может быть предпочтительным.Нажимая «Регистрация» или «Войти через Google», вы соглашаетесь с Публичной офертой, даете Согласие на обработку персональных данных, а также подтверждаете что вам есть 18 лет
Нажимая «Регистрация» или «Войти через Google», вы соглашаетесь с Публичной офертой, даете Согласие на обработку персональных данных, а также подтверждаете что вам есть 18 лет