Python

Python Имеется неупорядоченный массив из n различных целых чисел от 0 до n (0,1,…,j-1,j+1,….,n).

Имеется неупорядоченный массив из n различных целых чисел от 0 до n (0,1,…,j-1,j+1,….,n). Необходимо за один цикл определить недостающее число j.
ПОЖАЛУЙСТА, НАПИШИТЕ ПОЯСНЕНИЕ К РЕШЕНИЮ ЗАДАЧИ.
Владимир Кириченко
Владимир Кириченко
160
list(set(range(min(M),max(M)))-set(sorted(M)))
Находит все пропуски (если там даже не один)

>>> M=[0,1,2,3,4,5,6,7,9,10,11,12,13,14,15,16]
>>> list(set(range(min(M),max(M)))-set(sorted(M)))
[8]
>>> M=[0,1,2,3,4,5,6,7,9,10,11,12,13,15,16,17]
>>> list(set(range(min(M),max(M)))-set(sorted(M)))
[8, 14]
>>>
Владимир .
Владимир .
7 982
Лучший ответ
Владимир Кириченко Можете подробнее объяснить, что означает каждая функция?
(Я не опытный программист)
list(set(range(min(M),max(M)))-set(sorted(M)))
В простейшем случае, когда числа это арифметическая прогрессия 0,1,…,j-1,j+1,….,n
# a -- неупорядоченный массив
# n -- заранее известное число n
sum(range(n)) - sum(a)
# если число n не известно
sum(range(len(a)+1)) - sum(a)
101Zb Мгудт
101Zb Мгудт
22 178
По-моему, если каждый элемент проверять с помощью оператора "in", то по сути нарушается условие "за один цикл", так как по сути при каждом запросе "in" выполняется отдельный цикл, поэтому время выполнения квадратично.

По-моему вот так:
from random import shuffle, seed, randint
from time import time

seed(0)

N = 20_000
print('N =', N)

N += 1
a = [i for i in range(N)]
a.pop(randint(0, N-1))
shuffle(a)

st = time()
x = 0
for i in range(len(a)):
~~~~x += i - a[i]
x += i + 1
print(x)
print(time()-st)

# А это пример поиска с помощью оператора "in". Который предложил Иван Чудин.
st = time()
# a=(...) ваш кортеж c n-1 членами, от 0 до n-1, за минусом одного значения
j=-1 # инициализируем значение, который потом, проверим, были-ли изменения
for i in range(len(a)+1):
~~~~if not i in a:
~~~~~~~~j=i
~~~~~~~~break
if j==-1:
~~~~print("В процессе поиска пропущеный элемент не был найден")
else:
~~~~print("Пропущеный элемент: ",j)

print(time()-st)

Результаты запусков для N = 1000, 10_000, 20_000
Хорошо видно разницу в том, как увеличивается время выполнения с ростом числа элементов, без использования "in" и при его использовании.
==================
N = 1000
864
0.006000995635986328
Пропущеный элемент: 864
0.02500295639038086
>>>
==================
N = 10000
6311
0.00900125503540039
Пропущеный элемент: 6311
1.1166417598724365
>>>
==================
N = 20000
12623
0.013001680374145508
Пропущеный элемент: 12623
4.256540536880493
>>>

PS
У меня нет проверки на случай, когда пропущенного элемента нет.
Так как я посчитал, что условие задания не предусматривает такого случая. По условию один, и только один, элемент обязательно пропущен. А то если расширять условие, то надо еще предусматривать случаи когда пропущено больше одного.
Сергей Милов
Сергей Милов
21 729
тут читабельно и с отступами код https://onlinegdb.com/rJ6N7MiuO, что там пояснять не очень понимаю, все просто, но если будут вопросы - спрашивайте.
Алексей Слипченко
Алексей Слипченко
5 910
Владимир Кириченко Не знаю правильно ли я понял задание, но у меня получилось его реализовать таким кодом:
import random
from random import randint
n=int(input())
a = [i for i in range(0,n+1)]
random.shuffle(a)
e=sum(a)
x=randint(0,n)
a.pop(x)
f=sum(a)
g=e-f
print('В массиве отсутствует цифра: ',g)
Алексей Слипченко и где здесь "Необходимо за один цикл определить недостающее число j" ? :)
Ответ то вы получаете и он даже будет верным, но условия задачи не выполняете :)
то что вы перемешиваете массив делает его не отсортированным, но не делает его неупорядоченым, на мой взгляд, но тут уже и я могу не так понимать постановку данной учебной задачи.
смысл того кода, что привел я, мы в цикле берем число и проверяем присутствует ли оно в наборе закрепленном за переменной а. (причем это может быть и массив и множество и кортеж, зависит от того как вы a зададите) Если не присутствует, то это и есть исключенный элемент, его запоминаем и выводим.

Похожие вопросы