una - suma de matrices en java con metodos




Java: Comprobar la igualdad de las matrices(el orden no importa) (7)

Tengo dos matrices de String , digamos:

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

// estas matrices deben ser iguales

Quería comprobar su igualdad de la manera más "limpia".

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

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


Set::equals

NB: Esta es una solución simple y no intrusiva, pero solo funciona si está seguro de que no hay entradas duplicadas en ninguna de las matrices / listas de entrada (o si desea ignorar los duplicados).

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

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);
}

La forma humana:

Iterar sobre la primera matriz, verificando 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, tendría que, para cada elemento que está verificando, volver al principio y contar cuántas instancias de ese elemento hay (decir X), y solo contar un éxito como encontrar el elemento Xth en el segunda matriz Hacer esto eliminaría la necesidad de realizar la segunda verificación, y lo dejaría como un ejercicio para el lector (si 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: ordena ambas matrices y recorre ambas. 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: use un mapa hash, agregando para los conteos de la primera matriz de cadenas, eliminando los conteos de la segunda matriz de cadenas. Cuando estás odne todas las cuentas 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;
}

Para arreglos pequeños, usaría Arrays.sort y Arrays.equals como otros han sugerido. Para matrices más grandes, puede usar la siguiente solución que tiene mejor complejidad de tiempo: O(n) 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;
}

Primero ordenaría las 2 matrices, luego compararía 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;
}

Si está utilizando Eclipse Collections (anteriormente GS Collections ), puede usar una Bag para averiguar 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);

Las bolsas (también conocidas 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 usar una bolsa respaldada por una tabla hash es que crear una toma tiempo lineal. Ordenar ambas tomas O (n log n).

Nota: Soy un comendador de Eclipse Collections.


Supongo que esto es para la escuela.

Posibles estrategias:

  • use Arrays.sort para ordenar ambas matrices y luego use un bucle para comparar s1 [i] a s2 [i]
  • use un bucle y para cada elemento de s1 mire los elementos de s2 para encontrar si contiene el mismo
  • ponga los elementos de s1 en un hashset y luego use un bucle en s2 y observe si sus elementos están en s1

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

En caso de que no quiera modificar los arreglos originales.

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

Arrays.sort () utiliza una ordenación rápida optimizada que es nlog (n) para el promedio pero O (n2) en el peor de los casos. De los documentos java. Entonces, en el peor de los casos, será O (n2), pero en la práctica será O (nlogn) para la mayoría de los casos.

El algoritmo de clasificación es una secuencia rápida sintonizada, adaptada de Jon L. Bentley y "Ingeniería de una función de clasificación" de M. Douglas McIlroy, Software-Practice and Experience, vol. 23 (11) P. 1249-1265 (noviembre de 1993). Este algoritmo ofrece n * log (n) rendimiento en muchos conjuntos de datos que hacen que otras órdenes rápidas se degraden a rendimiento cuadrático.





string