Java: Comprobación de la igualdad de las matrices (el orden no importa)

Question

Tengo dos String matrices, digamos:

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

// estas matrices deben ser iguales

quería comprobar su igualdad en la manera "más limpia".

Intenté usar Arrays.equals(s1,s2) pero recibo una respuesta falsa. Supongo que este método se preocupa por el orden de los elementos y no quiero que eso importe.

¿Puede decirme cómo puedo hacer eso de una manera agradable?

Answer 1

• Arrays.sort (s1);
• Arrays.sort (s2);
• Arrays.equals (s1, s2);

En caso de que no desea modificar las matrices originales

Arrays.equals(Arrays.sort(Arrays.copyof(s1,s1.length)), 
       Arrays.sort(Arrays.copyof(s2,s2.length))); 

Arrays.sort() utiliza un tipo optimizado rápida que es n log (n) para la media, pero O (n2) en el peor de los casos . De los documentos de Java. Entonces, el peor caso será O (n2) pero prácticamente será O (nlogn) para la mayoría de los casos.

El algoritmo de clasificación es un quicksort sintonizado, adaptado de Jon L. Bentley y M. Douglas McIlroy, "Engineering a Sort Function", Software-Practice and Experience, vol. 23 (11) P. 1249-1265 (noviembre de 1993). Este algoritmo ofrece el rendimiento de n * log (n) en muchos conjuntos de datos que causan que otras soluciones rápidas se degraden a rendimiento cuadrático.

Answer 2

Supongo que esto es para la escuela.

estrategias posibles:

• uso Arrays.sort para ordenar ambas matrices y luego usar un bucle de comparar s1 [i] para s2 [i]
• utilizar un bucle y para cada elemento de la mirada s1 en los artículos de s2 para encontrar si contiene los mismos
• artículos de venta de s1 en un hashset y luego usar un bucle en S2 y mirar si sus artículos están en s1

Answer 3

String[] s1 = {"a","b","c"}; 
String[] s2 = {"b","c","a"} ; 

Arrays.sort(s1); 
Arrays.sort(s2); 

    if(Arrays.equals(s1, s2)){ 
     System.out.println("ok"); 
} 

Answer 4

Otros han sugerido la clasificación de las matrices. Pero dado que estás buscando la solución "más limpia", creo que las matrices originales no deberían tocarse. Por lo tanto:

List<String> l1 = new ArrayList<String>(Arrays.asList(s1)); 
List<String> l2 = new ArrayList<String>(Arrays.asList(s2)); 

Collections.sort(l1); 
Collections.sort(l2); 

boolean outcome = l1.equals(l2); 

Answer 5

La forma humana:

iterar sobre la primera matriz, la comprobación de la existencia de cada elemento en la segunda matriz, y luego hacer lo mismo para la segunda matriz en la primera matriz. Tiempo: n^2. Tenga en cuenta que este método supone que no se repite ningún elemento. Si lo fuera, deberías, para cada elemento que estás comprobando, volver al principio y contar cuántas instancias de ese elemento hay, (decir X), y solo contar un éxito como encontrar el X elemento en el segundo conjunto. Hacer esto eliminaría la necesidad del segundo control, y se lo dejaría como ejercicio al lector (si así lo desea, es decir.)

boolean equal(String[] arr1, String[] arr2) { 
    if(arr1.length != arr2.length) return false; // obviously 
    main_loop: 
    for(int i = 0; i < arr1.length; i++) { 
     for(int j = 0; j < arr2.length; j++) { 
      if(arr1[i].equals(arr2[j])) 
       break main_loop; 
     } 
     return false; 
    } 
    main_loop: 
    for(int i = 0; i < arr2.length; i++) { 
     for(int j = 0; j < arr1.length; j++) { 
      if(arr2[i].equals(arr1[j])) 
       break main_loop; 
     } 
     return false; 
    } 
    // having got through both loops, we can now return true 
} 

una forma más avanzada: ordenar ambas matrices y caminar sobre los dos. Tiempo: n lg n

boolean equals(String[] arr1, String[] arr2) { 
    if(arr1.length != arr2.length) return false; 
    String[] copy1 = Arrays.copyOf(arr1,arr1.length); // java.util.Arrays 
    String[] copy2 = Arrays.copyOf(arr2,arr2.length); // java.util.Arrays 
    Arrays.sort(copy1); 
    Arrays.sort(copy2); 
    for(int i = 0; i < copy1.length; i++) { 
     if(!copy1[i].equals(copy2[i]) 
      return false; 
    } 
    return true; 
} 

Una forma aún más avanzada: utilizar un HashMap, añadiendo para los cargos de la primera matriz de cadenas, la eliminación de los recuentos de la segunda matriz de cadenas. Cuando eres odne, todos los recuentos deben ser cero.

boolean equal(String[] arr1, String[] arr2) { 
    if(arr1.length != arr2.length) return false; 
    Map<String, Integer> map1 = new HashMap<String,Integer>(); 
    for(String str : arr1) { 
     if(!map.containsKey(str)) { 
      map.put(str, 1); 
     } else { 
      map.put(str, map.get(str) + 1); // add to count inthe map 
     } 
    } 
    for(String str : arr1) { 
     if(!map.containsKey(str)) { 
      return false; // we have an element in arr2 not in arr1 - leave now 
     } else { 
      map.put(str, map.get(str) - 1); // remove to count inthe map 
     } 
    } 
    for(Integer count : map.values()) { 
     if(count.intValue() != 0) return false; 
    } 
    return true; 
} 

Answer 6

Me Clasificar los 2 arrays en primer lugar, a continuación, comparar línea por línea ...

public boolean areArraysEqual (String[] array1,String[] array2){  
    if (s1.length != s2.length){ 
     return false; 
     } 

    java.util.Arrays.sort(s1); 
    java.util.Arrays.sort(s2); 

    for (int i=0;i<s1.length;i++){ 
     if (! s1[i].equals(s2[i])){ 
      return false; 
     } 
    } 

return true; 
} 

Answer 7

Si está utilizando Eclipse Collections (anteriormente GS Collections), se puede utilizar un Bag la figura fuera si las dos matrices son iguales.

String[] s1 = {"a", "b", "c", "c"}; 
String[] s2 = {"c", "a", "b", "c"}; 

Bag<String> h1 = HashBag.newBagWith(s1); 
Bag<String> h2 = HashBag.newBagWith(s2); 
Assert.assertEquals(h1, h2); 

Bags (también conocidos como conjuntos múltiples) se consideran iguales si tienen el mismo número de ocurrencias de cada elemento. El orden no importa, y maneja adecuadamente los elementos duplicados. La ventaja de utilizar una bolsa respaldada por una tabla hash es que la creación de uno lleva tiempo lineal. Ordenar ambos toma O (n log n).

Nota: Soy un confirmador de Eclipse Colecciones

Answer 8

Si una frecuencia faltará para comparar matrices uno contra el otro sin modificar su contenido, puede ser útil para definir un tipo que encapsula un conjunto inmutable, una ordenados su versión, un recuento de secuencias de long que se garantiza único y al menos en su mayoría se correlaciona con la antigüedad del objeto, y una referencia inicialmente nula a otro objeto antiguo que se sabe que coincide. También puede ser útil almacenar en caché un valor hash que combine los valores hash de todos los elementos de la matriz.

Al usar este enfoque, la primera vez que se compara un objeto con algo (cualquier cosa) se requiere una clasificación, pero no después de eso. Además, si los objetos X e Y se encuentran iguales a Z, entonces la comparación entre X e Y podría informarlos como iguales sin tener que examinar realmente los contenidos de la matriz (si Z es mayor que X e Y, ambos se reportarán a sí mismos como iguales al mismo objeto más viejo, si X es el más joven e Y el más viejo, X sabrá que es igual a Z y Z sabrá que es igual a Y. Cuando X sea el próximo comparado con algo, descubrirá que lo más viejo que se sabe para ser igual a es Y, por lo que por supuesto sería igual a Y.

Tal enfoque produciría beneficios de rendimiento igualdad-comparación similar a internar, pero sin la necesidad de un diccionario internar.

Answer 9

Set::equals

No necesita ninguna biblioteca externa para este. Set<> ya tiene un método equals que hace una comparación de orden independiente.

public static <T> boolean areArraysEquivalent(T[] ary1, T[] ary2) { 
    if (ary1 == null) { 
     return ary2 == null; 
    } 

    if (ary2 == null) { 
     return false; 
    } 

    List<T> list1 = Arrays.asList(ary1); 
    List<T> list2 = Arrays.asList(ary2); 
    return areListsEquivalent(list1, list2); 
} 


public static <T> boolean areListsEquivalent(List<T> list1, List<T> list2) { 
    if (list1 == null) { 
     return list2 == null; 
    } 

    if (list2 == null) { 
     return false; 
    } 

    Set<T> set1 = new HashSet<>(list1); 
    Set<T> set2 = new HashSet<>(list2); 
    return set1.equals(set2); 
} 

Answer 10

Para arreglos pequeños, me gustaría utilizar Arrays.sort y Arrays.equals como han sugerido otros. Para arreglos más grandes puede usar la siguiente solución que tiene una mejor complejidad de tiempo: O(n) en lugar de O(n log n).

public static boolean haveSameElements(Object[] arr1, Object[] arr2) { 
    return arr1.length == arr2.length && counts(arr1).equals(counts(arr2)); 
} 

// Map.merge and method references require Java 8 
private static <T> Map<T, Integer> counts(T[] arr) { 
    Map<T, Integer> map = new HashMap<>(); 
    for (T t : arr) 
     map.merge(t, 1, Integer::sum); 
    return map; 
}