Java – Eliminar duplicados en una ArrayList

Estoy trabajando en un progtwig que utiliza una ArrayList para almacenar Strings . El progtwig solicita al usuario un menú y le permite al usuario elegir una operación para realizar. Estas operaciones agregan cadenas a la lista, imprimen las entradas, etc. Lo que quiero poder hacer es crear un método llamado removeDuplicates() . Este método buscará ArrayList y eliminará cualquier valor duplicado. Quiero dejar una instancia de los valores duplicados dentro de la lista. También quiero que este método devuelva la cantidad total de duplicados eliminados.

He intentado utilizar bucles nesteds para lograr esto, pero he tenido problemas porque cuando se eliminan las entradas, la indexación de ArrayList se altera y las cosas no funcionan como deberían. Sé conceptualmente lo que debo hacer, pero tengo problemas para implementar esta idea en el código.

Aquí hay un pseudo código:

comenzar con la primera entrada; verifique cada entrada subsiguiente en la lista y vea si coincide con la primera entrada; eliminar cada entrada subsiguiente en la lista que coincida con la primera entrada;

después de que todas las entradas hayan sido examinadas, pase a la segunda entrada; verifique cada entrada en la lista y vea si coincide con la segunda entrada; eliminar cada entrada en la lista que coincida con la segunda entrada;

repetir para entrar en la lista

Aquí está el código que tengo hasta ahora:

 public int removeDuplicates() { int duplicates = 0; for ( int i = 0; i < strings.size(); i++ ) { for ( int j = 0; j < strings.size(); j++ ) { if ( i == j ) { // i & j refer to same entry so do nothing } else if ( strings.get( j ).equals( strings.get( i ) ) ) { strings.remove( j ); duplicates++; } } } return duplicates; } 

ACTUALIZACIÓN : parece que Will está buscando una solución de tareas que implique el desarrollo del algoritmo para eliminar duplicados, en lugar de una solución pragmática que use Conjuntos. Ver su comentario:

Gracias por las sugerencias. Esto es parte de una tarea y creo que la maestra tenía la intención de que la solución no incluyera conjuntos. En otras palabras, debo encontrar una solución que busque y elimine duplicados sin implementar un HashSet . La maestra sugirió usar bucles nesteds, que es lo que trato de hacer, pero he tenido algunos problemas con la indexación de ArrayList después de eliminar ciertas entradas.

¿Por qué no utilizar una colección como Set (y una implementación como HashSet ) que previene naturalmente los duplicados?

Puede usar bucles nesteds sin ningún problema:

 public static int removeDuplicates(ArrayList strings) { int size = strings.size(); int duplicates = 0; // not using a method in the check also speeds up the execution // also i must be less that size-1 so that j doesn't // throw IndexOutOfBoundsException for (int i = 0; i < size - 1; i++) { // start from the next item after strings[i] // since the ones before are checked for (int j = i + 1; j < size; j++) { // no need for if ( i == j ) here if (!strings.get(j).equals(strings.get(i))) continue; duplicates++; strings.remove(j); // decrease j because the array got re-indexed j--; // decrease the size of the array size--; } // for j } // for i return duplicates; } 

Puede probar este trazador de líneas para tomar una copia de la orden de conservación de cadenas.

 List list; List dedupped = new ArrayList(new LinkedHashSet(list)); 

Este enfoque también se amortiza O (n) en lugar de O (n ^ 2)

Solo para aclarar mi comentario sobre la respuesta de matt b, si realmente desea contar la cantidad de duplicados eliminados, use este código:

 List list = new ArrayList(); // list gets populated from user input... Set set = new HashSet(list); int numDuplicates = list.size() - set.size(); 
 List lst = new ArrayList(); lst.add("one"); lst.add("one"); lst.add("two"); lst.add("three"); lst.add("three"); lst.add("three"); Set se =new HashSet(lst); lst.clear(); lst = new ArrayList(se); for (Object ls : lst){ System.out.println("Resulting output---------" + ls); } 

He intentado utilizar bucles nesteds para lograr esto, pero he tenido problemas porque cuando se eliminan las entradas, la indexación de ArrayList se altera y las cosas no funcionan como deberían.

¿Por qué no disminuyes el contador cada vez que borras una entrada?

Cuando eliminas una entrada, los elementos se moverán también:

ej:

 String [] a = {"a","a","b","c" } 

posiciones:

 a[0] = "a"; a[1] = "a"; a[2] = "b"; a[3] = "c"; 

Después de eliminar su primera “a”, los índices son:

 a[0] = "a"; a[1] = "b"; a[2] = "c"; 

Por lo tanto, debe tener esto en cuenta y disminuir el valor de j ( j-- ) para evitar “saltar” sobre un valor.

Ver esta captura de pantalla:

esta funcionando

 public Collection removeDuplicates(Collection c) { // Returns a new collection with duplicates removed from passed collection. Collection result = new ArrayList(); for(Object o : c) { if (!result.contains(o)) { result.add(o); } } return result; } 

o

 public void removeDuplicates(List l) { // Removes duplicates in place from an existing list Object last = null; Collections.sort(l); Iterator i = l.iterator(); while(i.hasNext()) { Object o = i.next(); if (o.equals(last)) { i.remove(); } else { last = o; } } } 

Ambos no probados.

Una forma muy simple de eliminar cadenas duplicadas de araylist

 ArrayList al = new ArrayList(); // add elements to al, including duplicates HashSet hs = new HashSet(); hs.addAll(al); al.clear(); al.addAll(hs); 

Asumiendo que no puede usar un conjunto como usted dijo, la forma más fácil de resolver el problema es usar una lista temporal, en lugar de intentar eliminar los duplicados en su lugar:

 public class Duplicates { public static void main(String[] args) { List list = new ArrayList(); list.add("one"); list.add("one"); list.add("two"); list.add("three"); list.add("three"); list.add("three"); System.out.println("Prior to removal: " +list); System.out.println("There were " + removeDuplicates(list) + " duplicates."); System.out.println("After removal: " + list); } public static int removeDuplicates(List list) { int removed = 0; List temp = new ArrayList(); for(String s : list) { if(!temp.contains(s)) { temp.add(s); } else { //if the string is already in the list, then ignore it and increment the removed counter removed++; } } //put the contents of temp back in the main list list.clear(); list.addAll(temp); return removed; } } 

Podrías hacer algo así, lo que la gente respondió anteriormente es una alternativa, pero aquí hay otra.

 for (int i = 0; i < strings.size(); i++) { for (int j = j + 1; j > strings.size(); j++) { if(strings.get(i) == strings.get(j)) { strings.remove(j); j--; }` } } return strings; 

Usar un conjunto es la mejor opción para eliminar los duplicados:

Si tiene una lista de matrices, puede eliminar los duplicados y aún conservar las características de la lista de matrices:

  List strings = new ArrayList(); //populate the array ... List dedupped = new ArrayList(new HashSet(strings)); int numdups = strings.size() - dedupped.size(); 

si no puede usar un conjunto, ordene la matriz (Collections.sort ()) e itere sobre la lista, verificando si el elemento actual es igual al elemento anterior, si lo está, elimínelo.

Usar un conjunto es la mejor opción (como otros sugirieron).

Si quiere comparar todos los elementos de una lista, debe adaptar ligeramente sus bucles for:

 for(int i = 0; i < max; i++) for(int j = i+1; j < max; j++) 

De esta forma, no se compara cada elemento solo una vez en lugar de dos. Esto se debe a que el segundo ciclo comienza en el siguiente elemento en comparación con el primer ciclo.

Además, al eliminar de una lista al iterar sobre ellos (incluso cuando utiliza un bucle for en lugar de un iterador), tenga en cuenta que reduce el tamaño de la lista. Una solución común es mantener otra lista de elementos que desea eliminar, y luego de que haya terminado de decidir qué eliminar, los eliminará de la lista original.

 public ArrayList removeDuplicates(ArrayList  inArray) { ArrayList  outArray = new ArrayList(); boolean doAdd = true; for (int i = 0; i < inArray.size(); i++) { String testString = inArray.get(i); for (int j = 0; j < inArray.size(); j++) { if (i == j) { break; } else if (inArray.get(j).equals(testString)) { doAdd = false; break; } } if (doAdd) { outArray.add(testString); } else { doAdd = true; } } return outArray; } 

Podría reemplazar el duplicado con una cadena vacía *, manteniendo así la indexación intacta. Luego, una vez que haya completado, puede quitar las cadenas vacías.

* Pero solo si una cadena vacía no es válida en su implementación.

El problema que está viendo en su código es que elimina una entrada durante la iteración, lo que invalida la ubicación de la iteración.

Por ejemplo:

 {"a", "b", "c", "b", "b", "d"} ij 

Ahora estás eliminando cadenas [j].

 {"a", "b", "c", "b", "d"} ij 

El bucle interno finaliza y j se incrementa.

 {"a", "b", "c", "b", "d"} ij 

Solo se detectó un duplicado ‘b’ … oops.

La mejor práctica en estos casos es almacenar las ubicaciones que deben eliminarse y eliminarlas una vez que haya terminado de iterar a través de la lista de arrays. (Una ventaja, la llamada a strings.size () puede ser optimizada fuera de los bucles por usted o el comstackdor)

Sugerencia, puede comenzar a iterar con j en i + 1, ya ha comprobado el 0 – i!

El ciclo for interno no es válido. Si elimina un elemento, no puede incrementar j , ya que j ahora apunta al elemento después del que eliminó, y deberá inspeccionarlo.

En otras palabras, debe usar un ciclo while en lugar de un ciclo for , y solo incrementar j si los elementos en i y j no coinciden. Si coinciden, elimine el elemento en j . size() disminuirá en 1 y j ahora apuntará al siguiente elemento, por lo que no es necesario boost j .

Además, no hay ninguna razón para inspeccionar todos los elementos en el ciclo interno, solo los que siguen a i , ya que los duplicados ya han sido eliminados por iteraciones anteriores.

 public  Entry> uniqueElementList(List listWithPossibleDuplicates) { List result = new ArrayList();//...might want to pre-size here, if you have reliable info about the number of dupes Set found = new HashSet(); //...again with the pre-sizing for (Foo f : listWithPossibleDuplicates) if (found.add(f)) result.add(f); return entryFactory(listWithPossibleDuplicates.size()-found.size(), result); } 

y luego un entryFactory(Integer key, List value) . Si quieres mutar la lista original (posiblemente no es una buena idea, sino la que sea) en su lugar:

 public  int removeDuplicates(List listWithPossibleDuplicates) { int original = listWithPossibleDuplicates.size(); Iterator iter = listWithPossibleDuplicates.iterator(); Set found = new HashSet(); while (iter.hasNext()) if (!found.add(iter.next())) iter.remove(); return original - found.size(); } 

para su caso particular que utiliza cadenas de caracteres, es posible que necesite lidiar con algunas restricciones de igualdad adicionales (p. ej., ¿las versiones en mayúscula y minúscula son iguales o diferentes?).

EDITAR: ah, esto es tarea. Busque Iterator / Iterable en el marco de Java Collections, así como Set, y vea si no llega a la misma conclusión que ofrecí. La parte de los generics es solo salsa.

Estoy un poco tarde para unirme a esta pregunta, pero he llegado con una mejor solución con respecto al mismo tipo de GENERIC. Todas las soluciones proporcionadas anteriormente son solo una solución. Están aumentando la ventaja de la complejidad de todo el hilo de tiempo de ejecución.

RemoveDuplicacy.java

Podemos minimizarlo usando una técnica que debería hacer lo requerido, en el tiempo de carga.

Ejemplo: Supongamos que usa una lista de arrays del tipo de clase como:

 ArrayList usersList = new ArrayList(); usersList.clear(); User user = new User(); user.setName("A"); user.setId("1"); // duplicate usersList.add(user); user = new User(); user.setName("A"); user.setId("1"); // duplicate usersList.add(user); user = new User(); user.setName("AB"); user.setId("2"); // duplicate usersList.add(user); user = new User(); user.setName("C"); user.setId("4"); usersList.add(user); user = new User(); user.setName("A"); user.setId("1"); // duplicate usersList.add(user); user = new User(); user.setName("A"); user.setId("2"); // duplicate usersList.add(user); } 

La clase para la cual es la base para el arraylist utilizado anteriormente: clase de usuario

 class User { private String name; private String id; /** * @param name * the name to set */ public void setName(String name) { this.name = name; } /** * @return the name */ public String getName() { return name; } /** * @param id * the id to set */ public void setId(String id) { this.id = id; } /** * @return the id */ public String getId() { return id; } 

}

Ahora en Java hay dos métodos anulados presentes de la clase Object (parent), que pueden ayudar aquí en los medios para servir mejor a nuestro propósito. Ellos son:

 @Override public int hashCode() { final int prime = 31; int result = 1; result = prime * result + ((id == null) ? 0 : id.hashCode()); return result; } @Override public boolean equals(Object obj) { if (this == obj) return true; if (obj == null) return false; if (getClass() != obj.getClass()) return false; User other = (User) obj; if (id == null) { if (other.id != null) return false; } else if (!id.equals(other.id)) return false; return true; } 

Tienes que anular estos métodos en la clase de usuario

Aquí está el código completo:

https://gist.github.com/4584310

Déjeme saber si usted tiene cualquier pregunta.

Puede agregar la lista a un HashSet y luego convertir ese hashset a la lista para eliminar los duplicados.

 public static int removeDuplicates(List duplicateList){ List correctedList = new ArrayList(); Set a = new HashSet(); a.addAll(duplicateList); correctedList.addAll(a); return (duplicateList.size()-correctedList.size()); } 

aquí devolverá la cantidad de duplicados. También puede usar la lista correcta con todos los valores únicos

A continuación se muestra el código para eliminar elementos duplicados de una lista sin cambiar el orden de la lista, sin utilizar la lista temporal y sin utilizar ninguna variable establecida. Este código guarda la memoria y aumenta el rendimiento.

Este es un método genérico que funciona con cualquier tipo de lista.

Esta fue la pregunta formulada en una de las entrevistas. Busqué en muchos foros la solución pero no pude encontrarla, así que pensé que este es el foro correcto para publicar el código.

  public List removeDuplicate(List listWithDuplicates) { int[] intArray = new int[listWithDuplicates.size()]; int dupCount = 1; int arrayIndex = 0; int prevListIndex = 0; // to save previous listIndex value from intArray int listIndex; for (int i = 0; i < listWithDuplicates.size(); i++) { for (int j = i + 1; j < listWithDuplicates.size(); j++) { if (listWithDuplicates.get(j).equals(listWithDuplicates.get(i))) dupCount++; if (dupCount == 2) { intArray[arrayIndex] = j; // Saving duplicate indexes to an array arrayIndex++; dupCount = 1; } } } Arrays.sort(intArray); for (int k = intArray.length - 1; k >= 0; k--) { listIndex = intArray[k]; if (listIndex != 0 && prevListIndex != listIndex){ listWithDuplicates.remove(listIndex); prevListIndex = listIndex; } } return listWithDuplicates; }