Eliminar duplicados de la matriz en SWIFT 3.0 -- performance campo con programming-challenge campo con array campo con swift campo con set camp codereview Relacionados El problema

Remove Duplicates from Array in Swift 3.0


2
vote

problema

Español

Hice el siguiente código a través de un desafío de leetcode.com y dice que el tiempo de ejecución para los casos de prueba es de 119 ms, lo que lo pone en la parte posterior del paquete de rendimiento sabio.

El objetivo es eliminar duplicados de una matriz ordenada de ints y devolver el recuento de la matriz sin dups.

  skew.CalibrationDate.Date == (from skew2 in db.Skew                                where skew2.CalibrationDate.Date <= date.Date                                select skew2.CalibrationDate).Max() 1  

Pensé que mi solución era bastante simple, pero 119ms no está tan caliente en comparación con el promedio de ~ 60-70 ms. ¿Hay una mejor manera de hacer esto?

Original en ingles

I ran the following code through a Leetcode.com challenge and it says the runtime for the test cases is 119ms, which puts it at the back of the pack performance wise.

The goal is to remove duplicates from a sorted array of Ints and return the count of the array without dups.

func removeDuplicates(_ nums: inout [Int]) -> Int {     nums = Array(Set(nums)).sorted()     return nums.count } 

I thought my solution was pretty simple, but 119ms isn't so hot compared with the average of ~60-70ms. Is there a better way to do this?

              

Lista de respuestas

4
 
vote
vote
La mejor respuesta
 

Su código funciona correctamente, por lo que puedo ver. Una pequeña simplificación seria

  if2  

porque if3 se puede aplicar directamente a cualquier colección de Elementos comparables y devuelve una matriz.

Sin embargo, su código no se aprovecha del hecho de que la La matriz dada ya está ordenada. Dos colecciones intermedias (un conjunto y se crean una matriz), y la nueva matriz está ordenada. Que puede ser mejorado.

Dado que los elementos de la matriz están ordenados, puede atravesar todo elementos y solo mantenga aquellos que son diferentes a la anterior una. Esto lleva a la siguiente implementación:

  if4  

Además, puede guardarlo Memoria al sobrescribir los elementos en la matriz dada directamente. Si se encuentra un elemento diferente, entonces Se copia directamente a su nueva posición. Al final del bucle, Se eliminan los elementos excedentes:

  if5  

En mis pruebas, los dos últimos métodos fueron sobre un factor 10 más rápido que el tuyo.

 

Your code works correctly, as far as I can see. A small simplification would be

func removeDuplicates(_ nums: inout [Int]) -> Int {     nums = Set(nums).sorted()     return nums.count } 

because sorted() can directly be applied to any collection of comparable elements and returns an array.

However, your code does not take advantage of the fact that the given array is already sorted. Two intermediate collections (a set and an array) are created, and the new array is sorted. That can be improved.

Since the array elements are sorted, you can traverse through all elements and only keep those which are different to the previous one. This leads to the following implementation:

func removeDuplicates(_ nums: inout [Int]) -> Int {      guard let first = nums.first else {         return 0 // Empty array     }     var current = first     var uniqueNums = [current] // Keep first element      for elem in nums.dropFirst() {         if elem != current {             uniqueNums.append(current) // Found a different element             current = elem         }     }     nums = uniqueNums     return uniqueNums.count } 

In addition, you can save memory by overwriting the elements in the given array directly. If a different element is found then it is copied directly to its new position. At the end of the loop, surplus elements are removed:

func removeDuplicates(_ nums: inout [Int]) -> Int {      guard let first = nums.first else {         return 0 // Empty array     }     var current = first     var count = 1      for elem in nums.dropFirst() {         if elem != current {             nums[count] = elem             current = elem             count += 1         }     }      nums.removeLast(nums.count - count)     return count } 

In my tests, the last two methods were about a factor 10 faster than yours.

 
 
 
 

Relacionados problema

1  Set persistente (árbol negro rojo) - seguimiento  ( Persistent set red black tree follow up ) 
Seguimiento de esta pregunta cosas que cambié: arreglado algunos typos variables y métodos renombrados a nombres más descriptivos. (Eliminado 1 varia...

2  Set persistente (árbol negro rojo)  ( Persistent set red black tree ) 
Esta es una estructura de datos parcialmente persistente utilizando un árbol negro rojo. Se copiarán $ O (LG (N)) $ artículos para cada operación eliminar o...

11  Programa de chat "ai"  ( Ai chat program ) 
He lanzado este simple programa de chat, y mientras funciona. Creo que ciertamente podría usar alguna mejora. Así es como funciona. Obtenga la entrada del ...

1  Optimización divisible de subconjunto más grande  ( Largest divisible subset optimization ) 
Entonces, esta es mi solución al siguiente problema de leetcode: https: // leetcode .com / problemas / mayor-divisible-subconjunto / descripción / ¿Cómo p...

7  Forma más rápida de comparar conjuntos genéricos  ( Faster way of comparing generic sets ) 
El siguiente método de extensión es el factor limitante en el desempeño de una solicitud que estoy desarrollando, según Visual Studio 2012 Performance Analysi...

3  Encontrar la cantidad de formas de particionar {1,2, ..., n} en P1 y P2 de tal manera que suma (P1) == SUM (P2)  ( Finding the number of ways to partition 1 2 n into p1 and p2 such that s ) 
Estoy tratando de escribir un algoritmo de espacio y tiempo eficiente para calcular la cantidad de formas de particionar un conjunto de enteros {1, 2, ..., n}...

2  Disyointset con O (1) Encuentre y o (1) Unión amortizada  ( Disjointset with o1 find and o1 amortised union ) 
¿Este código supera la implementación común con la compresión de ruta y la unidad por rango? Todavía estoy de acuerdo con una revisión. github import j...

1  Posibles combinaciones de letras de una almohadilla de marcación en tiempo lineal utilizando un enfoque recursivo  ( Possible letter combinations of a dial pad in linear time using a recursive appr ) 
complejidad de tiempo: Camino la matriz de llaves inzagonadas inicial que representan el número O (n) hacia atrás. Luego hago un paseo interno de la matriz de...

3  Prueba para una matriz que es un subconjunto de otra matriz maestra  ( Test for an array being subset of another master array ) 
Estaba intentando construir una pequeña función de utilidad para verificar si una matriz es parte de otra matriz. Está probando si una matriz es un subconjunt...

7  Convierta una lista de conjuntos en la lista mínima de conjuntos que no sean intersectores  ( Convert a list of sets into the minimum list of non intersecting sets ) 
Tengo una lista de conjuntos. Los mismos elementos pueden aparecer en varios conjuntos. Quiero transformar esto en una nueva lista de conjuntos donde: Ca...




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