Devolver el primer duplicado -- python campo con algorithm campo con array camp codereview Relacionados El problema

Return first duplicate


15
vote

problema

Español

Este es un problema de CODESSIGNAL.

Las restricciones garantizadas son 9988777665544332 , y 1 <= a[i] <= a.length3 .

Tiene que devolver el primer duplicado Encoutered en a , OR -1 Si no se encuentra duplicado.

  def firstDuplicate(a):      b = [0] * 100001     for num in a:         if b[num] == 1:             return num         else:             b[num] = 1     return -1   

¿Hay una mejor manera de hacer esto? ¿Quizás más rápido o usando menos memoria? El índice no utilizado 0 en el b La matriz también no se siente muy limpia.

Original en ingles

This is a problem from Codesignal.

The guaranteed constraints are 1 <= a.length <= 10^5, and 1 <= a[i] <= a.length.

You have to return the first duplicate encoutered in a, or -1 if no duplicate is found.

def firstDuplicate(a):      b = [0] * 100001     for num in a:         if b[num] == 1:             return num         else:             b[num] = 1     return -1 

Is there a better way to do this? Perhaps faster or using less memory? The unused 0 index in the b array also doesn't feel very clean.

        
         
         

Lista de respuestas

8
 
vote
vote
La mejor respuesta
 

Memoria

Usos de implementación de su lista (según su arquitectura) 8 bytes por elemento de lista.

  int0  

NOTA: Este es solo el recuerdo de la estructura de la lista en sí. En general, los contenidos de la lista utilizarán memoria adicional. En la versión "original", esto sería punteros a dos constantes enteras ( int1 y int2 ); En la versión "Original_improved", estaría almacenando punteros a los dos singletos booleanos ( 99887776555443313 y int4 ). Dado que solo estamos almacenando referencias a dos objetos en cada caso, esta memoria adicional es insignificante, por lo que lo ignoraremos.


800KB de memoria no es una cantidad enorme, pero para ser cortés, podemos reducirlo:

  int5  

update : int6 es una mejor opción que int7 !

  int8  

El int9 crea una gran cantidad de bytes. A diferencia de las listas, que pueden almacenar diferentes tipos de cosas en cada elemento de la lista, el ByteTarray, como su nombre lo indica, solo almacenará bytes.

Con esta nueva estructura, ahora usamos solo 1 byte por bandera, por lo que alrededor de 100kb de memoria:

  len0  

Sabe de rendimiento, esta solución está cerca de la velocidad original, por lo que no estamos renunciando a ninguna velocidad significativa al tiempo que reduce la carga de la memoria a alrededor del 12,5%.


todavía podemos hacerlo mejor. El uso de un byte completo para una sola bandera es un desperdicio; Podemos apretar 8 banderas en cada byte. La 99887766555443321 Class hace todo el levantamiento pesado para nosotros:

  len2  

Esto nos lleva a 12.5kb para la matriz de banderas de bits. Desafortunadamente, esta optimización de memoria adicional viene con un golpe de velocidad adicional, debido al embalaje del bit y el desempaque. El rendimiento sigue siendo mejor que el rendimiento "SRIV_IMPRADO", y estamos usando solo 1/64 de los requisitos de memoria original.


Tiempo, en mi máquina:

  99887766555443323  
 

Memory

Your list implementation uses (depending on your architecture) 8 bytes per list element.

>>> import sys >>> b = [False] * 100001 >>> sys.getsizeof(b) 800064 

Note: This is just the memory of the list structure itself. In general, the contents of the list will use additional memory. In the "original" version, this would be pointers to two integer constants (0 and 1); in the "original_improved" version, it would be storing pointers to the two boolean singletons (False and True). Since we're only storing references to two objects in each case, this additional memory is insignificant, so we'll ignore it.


800kB of memory is not a huge amount, but to be polite, we can reduce it:

import array  def aneufeld_array(a):     b = array.array('b', (0,)) * (len(a) + 1)      for num in a:         if b[num]:             return num         b[num] = 1      return -1 

Update: bytearray is a better choice than array.array('b', ...)!

def aneufeld_bytearray(a):     b = bytearray(len(a) + 1)      for num in a:         if b[num]:             return num         b[num] = 1      return -1 

The bytearray(size) creates a tightly packed of bytes. Unlike lists, which can store different kinds of things in each element of the list, the bytearray, as its name implies, will only store bytes.

With this new structure, we now use only 1 byte per flag, so around 100kB of memory:

>>> b = bytearray(100001) >>> sys.getsizeof(b) 100058 

Performance wise, this solution is close to the original speed, so we're not giving up any significant speed while reducing the memory load to around 12.5%.


We can still do better. Using an entire byte for a single flag is wasteful; we can squeeze 8 flags into each byte. The bitarray class does all of the heavy lifting for us:

import bitarray  def aneufeld_bitarray(a):     b = bitarray.bitarray(len(a) + 1)     b.setall(False)      for num in a:         if b[num]:             return num         b[num] = True      return -1 

This gets us down to 12.5kB for the bit-array of flags. Unfortunately, this additional memory optimization comes with an additional speed hit, due to the bit packing and unpacking. The performance is still better than "Sriv_improved" performance, and we're using only 1/64th of the original memory requirement.


Timing, on my machine:

 4.94 ms   4.62 ms   4.55 ms  original  3.89 ms   3.85 ms   3.84 ms  original_improved 20.05 ms  20.03 ms  19.78 ms  hjpotter92  9.59 ms   9.69 ms   9.75 ms  Reinderien  8.60 ms   8.68 ms   8.75 ms  Reinderien_improved 19.69 ms  19.69 ms  19.40 ms  Sriv 13.92 ms  13.99 ms  13.98 ms  Sriv_improved  6.84 ms   6.84 ms   6.86 ms  aneufeld_array  4.76 ms   4.80 ms   4.77 ms  aneufeld_bytearray 12.71 ms  12.65 ms  12.57 ms  aneufeld_bitarray  
 
 
         
         
18
 
vote

Propondré una implementación alternativa, porque los diccionarios son buenos para almacenar pares de valor clave y no le importa el valor:

  len4  

Un conjunto lo comprará básicamente el mismo comportamiento que las "llaves de un diccionario" para estos fines.

 

I'll propose an alternate implementation, because dictionaries are good at storing key-value pairs and you don't care about the value:

def first_duplicate(given_list):     seen = set()     for value in given_list:         if value in seen:             return value         seen.add(value)     return -1 

A set will buy you basically the same behaviour as the "keys of a dictionary" for these purposes.

 
 
         
         
14
 
vote

Benchmark y versiones ligeramente mejoradas de algunas soluciones.

Felicidades, en el peor de los casos ( a = list(range(1, 10**5 + 1)) ) Su solución original es de aproximadamente 2-4.5 veces más rápido que las soluciones en las respuestas anteriores:

   5.45 ms   5.46 ms   5.43 ms  original  4.58 ms   4.57 ms   4.57 ms  original_improved 25.10 ms  25.59 ms  25.27 ms  hjpotter92 11.59 ms  11.69 ms  11.68 ms  Reinderien 10.33 ms  10.47 ms  10.45 ms  Reinderien_improved 23.16 ms  23.07 ms  23.02 ms  Sriv 17.00 ms  16.97 ms  16.94 ms  Sriv_improved   

Hecho con Python 3.9.0 64 bits en Windows 10 64 bits.

original_improved es suyo pero más rápido al no hacer == 1 y usando False en lugar de 0 , como eso es más rápido de reconocer como falso . Y para las listas de entrada más pequeñas, se necesita menos espacio, ya que hace b más pequeño en consecuencia.

Código:

  from timeit import timeit from collections import defaultdict  def original(a):     b = [0] * 100001     for num in a:         if b[num] == 1:             return num         else:             b[num] = 1     return -1  def original_improved(a):     b = [False] * (len(a) + 1)     for num in a:         if b[num]:             return num         b[num] = True     return -1  def hjpotter92(given_list):     seen = defaultdict(bool)     for value in given_list:         if seen[value]:             return value         seen[value] = True     return -1  def Reinderien(given_list):     seen = set()     for value in given_list:         if value in seen:             return value         seen.add(value)     return -1  def Reinderien_improved(given_list):     seen = set()     seen_add = seen.add           # Suggestion by Graipher     for value in given_list:         if value in seen:             return value         seen_add(value)     return -1  def Sriv(a):     for i in a:         if a[abs(i) - 1] > 0:             a[abs(i) - 1] *= -1         else:             return abs(i)     else:         return -1  def Sriv_improved(a):     for i in map(abs, a):         if a[i - 1] > 0:             a[i - 1] *= -1         else:             return i     else:         return -1  funcs = original, original_improved, hjpotter92, Reinderien, Reinderien_improved, Sriv, Sriv_improved  a = list(range(1, 10**5+1))  tss = [[] for _ in funcs] for _ in range(4):     for func, ts in zip(funcs, tss):         t = min(timeit(lambda: func(copy), number=1)                 for copy in (a.copy() for _ in range(50)))         ts.append(t)     for func, ts in zip(funcs, tss):         print(*('%5.2f ms ' % (t * 1000) for t in ts[1:]), func.__name__)     print()   
 

Benchmark and slightly improved versions of some solutions.

Congratulations, in the worst case (a = list(range(1, 10**5 + 1))) your original solution is about 2-4.5 times faster than the solutions in the previous answers:

 5.45 ms   5.46 ms   5.43 ms  original  4.58 ms   4.57 ms   4.57 ms  original_improved 25.10 ms  25.59 ms  25.27 ms  hjpotter92 11.59 ms  11.69 ms  11.68 ms  Reinderien 10.33 ms  10.47 ms  10.45 ms  Reinderien_improved 23.16 ms  23.07 ms  23.02 ms  Sriv 17.00 ms  16.97 ms  16.94 ms  Sriv_improved 

Done with Python 3.9.0 64-bit on Windows 10 64-bit.

original_improved is yours but faster by not doing == 1 and by using False instead of 0, as that's fastest to recognize as false. And for smaller input lists it takes less space as it makes b smaller accordingly.

Code:

from timeit import timeit from collections import defaultdict  def original(a):     b = [0] * 100001     for num in a:         if b[num] == 1:             return num         else:             b[num] = 1     return -1  def original_improved(a):     b = [False] * (len(a) + 1)     for num in a:         if b[num]:             return num         b[num] = True     return -1  def hjpotter92(given_list):     seen = defaultdict(bool)     for value in given_list:         if seen[value]:             return value         seen[value] = True     return -1  def Reinderien(given_list):     seen = set()     for value in given_list:         if value in seen:             return value         seen.add(value)     return -1  def Reinderien_improved(given_list):     seen = set()     seen_add = seen.add           # Suggestion by Graipher     for value in given_list:         if value in seen:             return value         seen_add(value)     return -1  def Sriv(a):     for i in a:         if a[abs(i) - 1] > 0:             a[abs(i) - 1] *= -1         else:             return abs(i)     else:         return -1  def Sriv_improved(a):     for i in map(abs, a):         if a[i - 1] > 0:             a[i - 1] *= -1         else:             return i     else:         return -1  funcs = original, original_improved, hjpotter92, Reinderien, Reinderien_improved, Sriv, Sriv_improved  a = list(range(1, 10**5+1))  tss = [[] for _ in funcs] for _ in range(4):     for func, ts in zip(funcs, tss):         t = min(timeit(lambda: func(copy), number=1)                 for copy in (a.copy() for _ in range(50)))         ts.append(t)     for func, ts in zip(funcs, tss):         print(*('%5.2f ms ' % (t * 1000) for t in ts[1:]), func.__name__)     print() 
 
 
 
 
11
 
vote

Tal vez, usando un diccionario para mantener la cuenta de valores ya visto?

  from collections import defaultdict  def first_duplicate(given_list):     seen = defaultdict(bool)     for value in given_list:         if seen[value]:             return value         seen[value] = True     return -1   

  1. El nombre de la función debe ser lower_snake_case .
  2. 5.45 ms 5.46 ms 5.43 ms original 4.58 ms 4.57 ms 4.57 ms original_improved 25.10 ms 25.59 ms 25.27 ms hjpotter92 11.59 ms 11.69 ms 11.68 ms Reinderien 10.33 ms 10.47 ms 10.45 ms Reinderien_improved 23.16 ms 23.07 ms 23.02 ms Sriv 17.00 ms 16.97 ms 16.94 ms Sriv_improved 0 inicializa con el valor predeterminado como 5.45 ms 5.46 ms 5.43 ms original 4.58 ms 4.57 ms 4.57 ms original_improved 25.10 ms 25.59 ms 25.27 ms hjpotter92 11.59 ms 11.69 ms 11.68 ms Reinderien 10.33 ms 10.47 ms 10.45 ms Reinderien_improved 23.16 ms 23.07 ms 23.02 ms Sriv 17.00 ms 16.97 ms 16.94 ms Sriv_improved 1 . Puede pasar 5.45 ms 5.46 ms 5.43 ms original 4.58 ms 4.57 ms 4.57 ms original_improved 25.10 ms 25.59 ms 25.27 ms hjpotter92 11.59 ms 11.69 ms 11.68 ms Reinderien 10.33 ms 10.47 ms 10.45 ms Reinderien_improved 23.16 ms 23.07 ms 23.02 ms Sriv 17.00 ms 16.97 ms 16.94 ms Sriv_improved 2 en lugar de 5.45 ms 5.46 ms 5.43 ms original 4.58 ms 4.57 ms 4.57 ms original_improved 25.10 ms 25.59 ms 25.27 ms hjpotter92 11.59 ms 11.69 ms 11.68 ms Reinderien 10.33 ms 10.47 ms 10.45 ms Reinderien_improved 23.16 ms 23.07 ms 23.02 ms Sriv 17.00 ms 16.97 ms 16.94 ms Sriv_improved 3
  3. Usa los nombres mejores / descriptivos de las variables.
  4. Dado que 5.45 ms 5.46 ms 5.43 ms original 4.58 ms 4.57 ms 4.57 ms original_improved 25.10 ms 25.59 ms 25.27 ms hjpotter92 11.59 ms 11.69 ms 11.68 ms Reinderien 10.33 ms 10.47 ms 10.45 ms Reinderien_improved 23.16 ms 23.07 ms 23.02 ms Sriv 17.00 ms 16.97 ms 16.94 ms Sriv_improved 4 está devolviendo un valor, no se necesita cláusula 5.45 ms 5.46 ms 5.43 ms original 4.58 ms 4.57 ms 4.57 ms original_improved 25.10 ms 25.59 ms 25.27 ms hjpotter92 11.59 ms 11.69 ms 11.68 ms Reinderien 10.33 ms 10.47 ms 10.45 ms Reinderien_improved 23.16 ms 23.07 ms 23.02 ms Sriv 17.00 ms 16.97 ms 16.94 ms Sriv_improved 5 .
 

Perhaps, using a dictionary to keep account of already seen values?

from collections import defaultdict  def first_duplicate(given_list):     seen = defaultdict(bool)     for value in given_list:         if seen[value]:             return value         seen[value] = True     return -1 

  1. Function name should be lower_snake_case.
  2. defaultdict initialises with default value as False. You can pass None instead of bool
  3. Use better/descriptive names of variables.
  4. Since if clause is returning a value, using the else clause is not needed.
 
 
     
     
7
 
vote

Tenga en cuenta que todos los elementos son positivos, y los valores no son mayores que la longitud.
Hay un método muy inteligente para encontrar la solución en estos casos.

La idea es marcar los valores girando 5.45 ms 5.46 ms 5.43 ms original 4.58 ms 4.57 ms 4.57 ms original_improved 25.10 ms 25.59 ms 25.27 ms hjpotter92 11.59 ms 11.69 ms 11.68 ms Reinderien 10.33 ms 10.47 ms 10.45 ms Reinderien_improved 23.16 ms 23.07 ms 23.02 ms Sriv 17.00 ms 16.97 ms 16.94 ms Sriv_improved 6 negativo.
Si existe un duplicado, se encontrará con 5.45 ms 5.46 ms 5.43 ms original 4.58 ms 4.57 ms 4.57 ms original_improved 25.10 ms 25.59 ms 25.27 ms hjpotter92 11.59 ms 11.69 ms 11.68 ms Reinderien 10.33 ms 10.47 ms 10.45 ms Reinderien_improved 23.16 ms 23.07 ms 23.02 ms Sriv 17.00 ms 16.97 ms 16.94 ms Sriv_improved 7 como negativo.

Aquí está la implementación:

   5.45 ms   5.46 ms   5.43 ms  original  4.58 ms   4.57 ms   4.57 ms  original_improved 25.10 ms  25.59 ms  25.27 ms  hjpotter92 11.59 ms  11.69 ms  11.68 ms  Reinderien 10.33 ms  10.47 ms  10.45 ms  Reinderien_improved 23.16 ms  23.07 ms  23.02 ms  Sriv 17.00 ms  16.97 ms  16.94 ms  Sriv_improved 8  

¡Asegúrese de convertir los valores a la indexación basada en 0!

Este enfoque es o (n) complejidad de tiempo y o (1) complejidad extra del espacio.

 

Note that all the elements are positive, and the values are not greater than the length.
There is a very clever method to find the solution in these cases.

The idea is to mark the values by turning a[value] negative.
If a duplicate exists, it will encounter a[duplicate] as negative.

Here's the implementation:

for i in a:     if a[abs(i) - 1] > 0:         a[abs(i) - 1] *= -1      else:         print(abs(i))         break  else:     print(-1) 

Make sure to turn the values to 0-based indexing though!

This approach is O(N) time complexity and O(1) extra space complexity.

 
 
         
         
4
 
vote

Usando la comprensión de la lista, haga una lista de los números que ocurren más de una vez

   5.45 ms   5.46 ms   5.43 ms  original  4.58 ms   4.57 ms   4.57 ms  original_improved 25.10 ms  25.59 ms  25.27 ms  hjpotter92 11.59 ms  11.69 ms  11.68 ms  Reinderien 10.33 ms  10.47 ms  10.45 ms  Reinderien_improved 23.16 ms  23.07 ms  23.02 ms  Sriv 17.00 ms  16.97 ms  16.94 ms  Sriv_improved 9  

Devuelve la primera coincidencia o -1 si no se encontró ninguna coincidencia

  original_improved0  
 

Using list comprehension, make a list of the numbers occurring more than once

i for i in a if a.count(i) > 1 

Return the first match or -1 if no match was found

next((i for i in a if a.count(i) > 1), -1) 
 
 
       
       

Relacionados problema

2  Importando datos en Excel  ( Importing data into excel ) 
¿Existe una forma más fácil de importar datos en una matriz de Excel u otra estructura de datos? He intentado investigar colecciones, pero he encontrado la D...

2  Devuelve verdadero si los elementos de una matriz no contienen uno u otro  ( Return true if the elements of an array do not contain one or the other ) 
Estoy completando gradualmente los ejercicios de codificación para Java. Aquí está el uno acabo de hacer: Dada una matriz de INTS, devuelva verdadera si ...

7  Colecciones vacías en caché  ( Cached empty collections ) 
A menudo necesito devolver las colecciones vacías. Uno de esos días, escribí lo siguiente para devolver una instancia en caché: public static class Array<...

6  Fusionando dos varias de clases  ( Merging two array of classes ) 
Tengo esta función que debe fusionar dos matriz de clases cuando id es igual a id de Array2. Para la simplicidad, convirtí una matriz en un arraylist pa...

2  Cargando imágenes en el fondo para una vista de tabla  ( Loading images in the background for a table view ) 
Tengo fetchData2 MÉTODO QUE LLENA MI imagesArray : func fetchData(){ let imageQuery = PFUser.query() imageQuery?.whereKey("username", contained...

6  Buscar número de más en una matriz 2D  ( Find number of plus in a 2d array ) 
Problema Chargrid El CharGrid La clase encapsula una matriz de 2-D con una pareja de operaciones. INT APULUS () Busque un patrón '+' en la cuadrícu...

6  Clase de matriz multidimensional simple en C ++ 11  ( Simple multi dimensional array class in c11 ) 
La nueva versión del código se puede revisar en Clase de matriz multidimensional simple en C ++ 11 - Seguimiento . El siguiente código implementa una clas...

6  Palindrome más largo en una matriz  ( Longest palindrome in an array ) 
Soy nuevo en la programación, y creo que este código podría mejorarse. ¿Alguna sugerencia? 'done'0 ...

5  Encuentra el primer número único de la matriz  ( Find first unique number from array ) 
Se me pidió que creara una función que devuelva el primer entero único de la matriz de enteros. En un caso de éxito, la función devuelve el número único en un...

2  Mejora de la función que compara dos cadenas  ( Improving function that compares two strings ) 
Estoy aprendiendo C y he hecho esta función muy simple para comparar dos cuerdas. Me gustaría saber cómo se puede mejorar: int match(char* string1, char* s...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos