Intersection of Two Arrays

+10

Recibes dos arreglos de enteros, nums1 y nums2. Devuelve cada valor que aparece en ambos arreglos, ordenado de menor a mayor. Cada valor compartido aparece una vez en la respuesta, sin importar cuántas veces se repita en cualquiera de los arreglos.

Función

intersection(nums1: integer-array, nums2: integer-array) → integer-array

nums1integer-array: la primera lista de números enteros
nums2integer-array: la segunda lista de números enteros
Devuelveinteger-array: los valores que se encuentran en ambas listas, cada uno una vez, en orden creciente

Restricciones

1 ≤ nums1.length, nums2.length ≤ 5000
-10⁵ ≤ nums1[i], nums2[i] ≤ 10⁵
Al menos un valor aparece en ambas matrices.

Ejemplos

Entrada: nums1 = [6, 2, 9, 2, 4]nums2 = [4, 4, 1, 6]
Salida: [4, 6]
Explicación: 4 y 6 están en ambos arreglos. 4 aparece dos veces en nums2, pero se enumera una sola vez, y 2 y 9 nunca aparecen en nums2.

Entrada: nums1 = [-3, 0, 7]nums2 = [7, -3, -3, 5]
Salida: [-3, 7]
Explicación: -3 y 7 están en ambos arreglos. En orden creciente, -3 va primero, aunque 7 aparece primero en nums2.

+16 pruebas ocultas al enviar

Para ir más allá

¿Qué pasaría si nums1 contiene 10 valores y nums2 contiene un millón y ya está ordenado? ¿Qué enfoque elegirías y puede la búsqueda binaria superar un recorrido completo?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Dos detalles determinan este problema: un valor que se repite en ambos lados aparece una sola vez en la respuesta, y la respuesta debe quedar ordenada. Comparar cada par funciona, pero cuesta n × m comparaciones, 2.5 × 10^7 cuando ambos arreglos contienen 5000 valores. Ordenar ambos arreglos permite que dos punteros encuentren los valores compartidos en orden, y un conjunto hash de uno de los arreglos responde «¿está este valor en nums1?» en tiempo constante.

Compara cada par

Correcto, pero no termina con las pruebas más grandes

Intuición

Toma cada valor de nums1 y recorre nums2 buscándolo. Detén el recorrido en la primera coincidencia y omite un valor que ya esté en la respuesta, así que [8, 8, 8, 8] frente a [8, 8] da un solo 8, no cuatro. Ordena la respuesta al final.

Es correcto porque un valor se incluye en la respuesta exactamente cuando alguna de sus copias en nums1 encuentra una coincidencia en nums2, y la omisión evita que se incluya dos veces.

Es lento porque cada valor de nums1 puede recorrer todo nums2. Con 5000 valores en cada arreglo, eso supone hasta 2.5 × 10^7 comparaciones, y en las pruebas grandes la mayoría de los valores no encuentra coincidencia, así que la mayoría de los recorridos llegan hasta el final.

Algoritmo

Empieza con una lista de respuestas vacía.
Para cada valor a de nums1, omítelo si ya está en la respuesta.
De lo contrario, recorre nums2; al encontrar el primer valor igual a a, agrega a a la respuesta y detén el recorrido.
Ordena la respuesta en orden creciente y devuélvela.

def intersection(nums1, nums2):
    result = []
    for a in nums1:
        if a in result:
            continue
        # Look for a anywhere in nums2.
        for b in nums2:
            if a == b:
                result.append(a)
                break
    result.sort()
    return result

Ordena ambos y después recórrelos con dos punteros

Intuición

Ordenado, el ejemplo 1 queda como [2, 2, 4, 6, 9] y [1, 4, 4, 6]. Coloca el puntero i al inicio del primer arreglo y j al inicio del segundo. El puntero que está sobre el valor más pequeño avanza: ese valor no puede coincidir con ningún valor más adelante en el otro arreglo, donde todos los valores son al menos igual de grandes. Cuando ambos punteros apuntan al mismo valor, ese valor es compartido, así que añádelo y mueve ambos punteros.

En el ejemplo: 2 > 1 mueve j, ambos 2 son menores que 4 y mueven i, 4 = 4 añade 4, el segundo 4 es menor que 6 y mueve j, y 6 = 6 añade 6. Un valor compartido varias veces en ambos lados, como 2 en [2, 2, 3] y [2, 2], coincide más de una vez; compararlo con el último valor añadido conserva una sola copia. El resultado queda ordenado sin ningún paso adicional.

Ordenar cuesta O(n log n + m log m), y el recorrido es O(n + m) porque cada paso mueve al menos un puntero. La mayoría de las versiones ordenan copias, lo que cuesta O(n + m) de memoria. Si puedes reordenar las entradas, ordénalas en el lugar, como hace el código C, y la única memoria adicional es la del resultado.

Algoritmo

Ordena ambos arreglos.
Establece i = 0 y j = 0.
Mientras ambos punteros estén dentro de sus arreglos, mueve el puntero que apunta al valor menor.
Si los valores son iguales, agrega el valor a menos que sea igual al último valor agregado; después, mueve ambos punteros.
Devuelve la respuesta.

def intersection(nums1, nums2):
    a = sorted(nums1)
    b = sorted(nums2)
    i, j = 0, 0
    result = []
    while i < len(a) and j < len(b):
        if a[i] < b[j]:
            i += 1
        elif a[i] > b[j]:
            j += 1
        else:
            # A shared value: keep it once, even if it repeats.
            if not result or result[-1] != a[i]:
                result.append(a[i])
            i += 1
            j += 1
    return result

Conjunto hash de la primera matriz

Intuición

Coloca cada valor de nums1 en un conjunto hash. En el ejemplo 1, el conjunto es {6, 2, 9, 4}: el 2 repetido se elimina al insertarlo. Después, recorre nums2 y consulta el conjunto por cada valor en tiempo constante. El primer 4 está, así que se añade a la respuesta. El segundo 4 no debe añadirse, así que elimina un valor del conjunto en el momento en que coincida. 1 no está y 6 sí, lo que da [4, 6].

Eliminar un valor cuando coincide es lo que hace que cada valor aparezca una sola vez: después de su primera coincidencia, el valor desaparece del conjunto, así que las copias posteriores en nums2 no encuentran nada. Cada valor añadido está en ambos arreglos, y cada valor compartido se añade cuando llega su primera copia en nums2.

Construir el conjunto y recorrer los valores toma O(n + m) en promedio. La respuesta se obtiene en el orden de nums2, así que ordénala al final; contiene k ≤ min(n, m) valores, lo que cuesta O(k log k). C no tiene un conjunto integrado, así que el código en C usa un arreglo de indicadores indexado por value + 10^5, que funciona porque los valores están acotados.

Algoritmo

Crea un conjunto hash first a partir de nums1.
Para cada valor de nums2, si está en first, añádelo a la respuesta y elimínalo de first.
Ordena la respuesta en orden creciente.
Devuélvela.

def intersection(nums1, nums2):
    first = set(nums1)
    result = []
    for num in nums2:
        if num in first:
            result.append(num)
            # Remove it so a repeat in nums2 is not added twice.
            first.remove(num)
    result.sort()
    return result

Errores comunes y casos límite

La mayoría de las respuestas incorrectas aquí se deben a los valores repetidos y al orden del resultado.

Añadir un valor cada vez que coincide. [2, 2, 3, 3, 3] y [3, 2, 2] tienen dos valores en común, así que la respuesta es [2, 3], no [3, 2, 2].
Devolver los valores en el orden en que los encontraste. El recorrido del conjunto hash sigue nums2, así que [7, -3] debe ordenarse para obtener [-3, 7].
Ordenar los números como texto. El método sort() de JavaScript, si no se le pasa un comparador, compara cadenas, así que [100000, 99] conserva ese orden. Pasa (x, y) => x - y.
Usar la intersección de conjuntos y olvidar el orden. set(nums1) & set(nums2) de Python encuentra los valores correctos sin ningún orden particular; envuélvelo en sorted.
Indexar un arreglo de indicadores usando el valor sin modificar. -3 no es un índice válido; primero desplaza todos los valores en 10^5.

Preguntas frecuentes4

¿Cuál es la complejidad temporal de la intersección de dos matrices?

Con un conjunto hash, encontrar los valores compartidos tarda O(n + m) en promedio, y ordenar los k valores de la respuesta añade O(k log k); el conjunto usa O(n) de espacio. Ordenar ambos arreglos y recorrerlos con dos punteros tarda O(n log n + m log m). Comparar cada par tarda O(n × m).

¿Deberías usar un conjunto hash o dos punteros?

Usa el conjunto hash cuando los arreglos no estén ordenados y haya memoria disponible: requiere el menor trabajo. Usa dos punteros cuando ambos arreglos ya estén ordenados o cuando la memoria sea limitada y puedas ordenarlos en el lugar. El recorrido no necesita un conjunto y produce la respuesta en orden.

¿Cómo conservas los valores repetidos en la intersección?

Si un valor debe aparecer tantas veces como aparece en ambos arreglos, de modo que [3, 1, 3, 3] y [3, 3] den [3, 3], reemplaza el conjunto por un mapa de conteo. Cuenta los valores de nums1 y, para cada valor de nums2 cuyo conteo sea mayor que cero, añádelo y reduce su conteo. En el recorrido con dos punteros, elimina la comprobación del último valor añadido.

¿Cómo se encuentra la intersección cuando un array es demasiado grande para la memoria?

Construye el conjunto hash a partir del arreglo que quepa y lee el más grande en partes, comprobando cada valor con el conjunto y eliminándolo si coincide. La memoria se mantiene al tamaño del arreglo más pequeño. Si no cabe ninguno de los arreglos, ordénalos ambos en disco y recórrelos con dos punteros sobre los archivos ordenados.

Python

def intersection(nums1, nums2):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Entrada

nums1 = [6, 2, 9, 2, 4]
nums2 = [4, 4, 1, 6]

Esperado

[4, 6]

Intersection of Two Arrays

Función

Restricciones

Ejemplos

Pistas

Solución

Compara cada par

Ordena ambos y después recórrelos con dos punteros

Conjunto hash de la primera matriz

Errores comunes y casos límite

Preguntas frecuentes4

Problemas similares