Cómo encontrar elementos comunes en 3 matrices ordenadas

Utilice tres índices A, B, C que apuntan al inicio de las matrices.
while (A Si todos los elementos son iguales (arr1 [A] == arr2 [B] == arr3 [C]) señalados por los índices, entonces es un elemento común e incrementa todos los índices en 1 (A ++, B ++, C ++)
más
obtenga el más pequeño de los tres elementos e incremente ese índice en 1. Ejemplo (si arr1 [A] }

Está obteniendo un bucle infinito porque no incrementa el i y j, por lo que while (i

if (arr1 [i] == arr2 [j]) {al.add (arr1 [i]); i ++, j ++;}
si no (arr1 [i] de lo contrario j ++;
Además, el segundo bucle no debe estar dentro del primero.

Aquí hay una solución generalizada para encontrar elementos comunes de n matrices ordenadas:

Encuentra elementos comunes en matrices ordenadas ‘n’

El algoritmo es el siguiente:

Se nos dan matrices ordenadas ‘n’, digamos matriz-1, matriz-2 a matriz-n. Para descubrir elementos comunes en estas matrices, seleccionamos cada elemento a partir del elemento en el índice 0 de la matriz-1 y verificamos si ese elemento está presente en todas las matrices restantes. Para verificar si un elemento de array-0 (elementArray0) está presente en array-‘i ‘(1 <= i <= n), comenzamos a mirar los elementos en array-'i' comenzando desde 'último índice verificado' hasta encontramos un elemento que es mayor o igual que el elemento de array-0 (elementArray0). Este último índice verificado se inicializaría a 0 para todas las matrices: matriz-1 a matriz-n. Nos detenemos cuando encontramos un elemento que es mayor o igual que 'elementArray0', guardamos este índice como 'último índice verificado' para array-'i 'y procedemos a array-'i + 1' para que coincida el elemento 'elementArray0'. Dado que array-'i 'está ordenado, no necesitamos verificar la coincidencia del índice 0 nuevamente cuando intentamos hacer coincidir el siguiente elemento de array-0. Este 'último índice verificado' se usaría para reanudar la operación de coincidencia para el siguiente elemento de array-0.

Espero que esto ayude.

Recorre las tres matrices en paralelo:

1. Cree tres variables de índice, cada una apuntando a la posición actual en una de las matrices. Comience con todas las variables de índice establecidas en 0.
2. Si los tres números en las posiciones del índice son iguales, usted encontró una coincidencia.
3. incremente el índice que apunta al valor más bajo (elija cualquiera si más de un índice apunta al mismo valor más bajo).
4. si el índice ahora está más allá del final de la matriz, deténgase.
5. Repita desde el paso 2

Esto está fuera de mi cabeza, después de explorar quora durante unas horas en lugar de irme a la cama … Así que no hay garantías de que esto realmente funcione 😉 Pero si lo hace, es O (n). Y debería funcionar incluso si las matrices tienen una longitud muy diferente.

EDITAR: Oh, no vi la respuesta de Adrian, se parece mucho a lo que tenía en mente. Responder directamente desde mi Feed es confuso, pierdo contexto …

¿Por qué no simplemente pasar por todos los elementos de la primera matriz y aplicar la búsqueda binaria en los otros dos?
Si su elemento se encuentra utilizando la búsqueda binaria en las otras dos matrices, puede insertarlo en la lista de elementos comunes.
La complejidad total es O (N (log (M) + log (P)).
Dónde;
N es la longitud de la primera matriz.
M es la longitud de la segunda matriz.
P es la longitud de la tercera matriz.

Una posible solución es usar una tabla hash para observar qué elementos han ocurrido cuántas veces; entonces es irrelevante cuántas matrices tiene o si están ordenadas: observa cuántas veces se ha producido un elemento de matriz determinado y cuando procesa la última matriz observa los elementos que ocurrieron en todas las matrices hasta el momento.