enlace del problema de leetcode

Se me ocurrieron dos soluciones escritas en Python pero no pasé y no sé por qué.

Dada una matriz de enteros donde 1 ≤ a [i] ≤ n (n = tamaño de la matriz), algunos elementos aparecen dos veces y otros aparecen una vez.

Encuentre todos los elementos de [1, n] inclusive que no aparecen en esta matriz.

Aquí está mi primera solución:

class Solution(object):
  def findDisappearedNumbers(self, nums):
     nums=sorted(list(set(nums)))
     for x in range(1, nums[-1] + 1):
       if x in nums:
         nums.remove(x)
       else:
         nums.append(x)
     return nums

El resultado es "Mensaje de error de tiempo de ejecución: línea 4: IndexError: índice de lista fuera de rango". Pero no lo entendí.

La segunda solución:

return [x for x in range(1, len(nums) + 1) if x not in nums]

El resultado es "Límite de tiempo excedido", aún confundido.

Ambas soluciones funcionan bien en mi Pycharm con python 2.7.11. Tal vez hay algunos casos de prueba que mis soluciones no pasaron pero no puedo encontrarlo.

1
Ficus 26 dic. 2016 a las 07:59

3 respuestas

La mejor respuesta

Su primera solución fallará si la entrada de prueba es una lista vacía ya que num [-1] daría un índice fuera de límite. Su segunda solución será lenta ya que tiene que recorrer la lista en iteración. ¿Funcionaría la siguiente solución? Las operaciones de set están optimizadas. ¿Pero la complejidad del espacio está bien para ti?

    ret = set(range(1, len(nums)+1))
    ret = ret - set(nums)
    return list(ret)
-1
Aditya 26 dic. 2016 a las 06:42

Desde la primera solución: NO modifique la lista que está iterando. Siempre trae problemas. ¡Mejor copie la lista y modifique la lista!

class Solution(object):
    def findDisappearedNumbers(self, nums):
        nums=sorted(list(set(nums)))
        nums_copy = nums.copy(nums)
        for x in range(1, nums[-1] + 1):
            if x in nums:
                nums_copy.remove(x)
            else:
                 nums_copy.append(x)
        return nums_copy

Por otro lado, si num es muy grande (tiene muchos elementos) range puede traer problemas porque crea la lista primero (y las listas MUY grandes ocupan MUCHA memoria). Para mí, es mejor xrange que devolver un generador Esto no sucede en python3, donde el range devuelve un generador.

0
Lucas 26 dic. 2016 a las 07:13

En primer lugar, intente usar xrange en lugar de range ya que esto usa menos espacio cuando el valor de nums es muy grande. Además, está intentando iterar, así como eliminar / agregar un valor al mismo tiempo en la misma matriz. Esta es probablemente la razón por la que está recibiendo el error.

Además, eliminar un valor de la lista (si no está al final) lleva mucho tiempo porque todos los demás elementos antes de que sea necesario moverlo.

0
apatniv 26 dic. 2016 a las 05:18