Estruturas de repetição avançada

Programação Python
,
#1

Boa tarde, fiz uma linha de programação para resolver esse problema da imagem a seguir porem a mesma se encontra com erros sintáticos e semânticos, gostaria de saber o que esta errado e o porque para mim entender melhor o raciocínio.

falta%20um%20programacao%20python
falta um programacao python.png912×664 49.9 KB

programação minha que esta errada.

n = input()
a = []
for x in input().split():
a.append(int(x))

cnt = {}
mis = {}

for i in range(n):
mis[i] = 1

dup = -1

for x in a:
if x in cnt:
cnt[x] = 0

cnt[x] += 1

if cnt[x] = 2:
    dup = x
else:
    mis.pop(x)

print(dup, list(mis.values())[0])

#2

Olhando o código por cima faltou realizar o cast nessa linha:

n = int(input)

Vou deixar aqui a minha implementação (não sei vai passar no tempo):

n = int(input())
numeros = [int(v) for v in input().split(' ')]
frequencia = {k: 0 for k in range(1, n+1)}
duplicado = None
alterado = None

for numero in numeros:
    frequencia[numero] += 1

for key, valor in frequencia.items():
    if valor == 0:
        alterado = key
    if valor == 2:
        duplicado = key
    if alterado and duplicado:
        break

print(duplicado, alterado)
#3

Primeiro, você pode ler os dados assim:

size = int(input())
arr = list(map(int, input().split()))

map aplica a função int aos elementos do array retornado por split, e depois list já transforma tudo em uma lista.

Já o algoritmo em si, você pode assim:

Como sabemos que o array sempre tem números de 1 a N e somente um deles é repetido (pois isso é garantido pelo enunciado), podemos aproveitar esta informação no algoritmo:

  • para cada número, use-o como a posição do array, e mude o elemento daquela posição para ter o valor negativo (ex: se for 2, passa a ser -2)
  • mas se esse elemento já for um número negativo, então a posição é o número repetido (pois já foi mudado anteriormente)
  • ao final, todos os elementos serão negativos, exceto aquele que está na posição correspondente ao número faltante

Lembrando que as posições de uma lista começam em zero, mas os números começam em 1, ou seja, tem que subtrair 1 para achar a posição correspondente:

size = int(input())
arr = list(map(int, input().split()))

for n in arr:
    # usa o número como posição
    pos = abs(n) - 1
    if arr[pos] > 0: # transforma o número naquela posição em negativo
        arr[pos] = -arr[pos]
    else: # mas se já é negativo, então ele é o duplicado
        duplicado = abs(n)

# o único que estiver positivo é o que está faltando
for i, n in enumerate(arr):
    if n > 0:
        faltando = i + 1
        break

print(duplicado, faltando)

Lembrando que esta solução modifica o array, mas se a ideia é só achar o que está duplicado e o faltante, não tem problema. Só precisamos percorrer o array duas vezes, e sem precisar de espaço extra (o enunciado diz para usar dicionário, mas na verdade nem precisa).