Change language
Python.Engineering Wiki Encuentre n + m-1 pares únicos de sumas para dos matrices.

Encuentre n + m-1 pares únicos de sumas para dos matrices.

array Python module | Arrays | ast Python module | code Python module | collections Python module | COM PHP module | FFI PHP module | http Python module | imp Python module | io Python module | Loops | PS PHP module | Python functions | re Python module | StackOverflow | time Python module
Michael Zippo Michael Zippo

Ejemplo:

Entrada:  N = 5, M = 3 A = [6, 5, 7, 1, 3] B = [2, 4, 8] Resultado:  2 0 2 1 2 2 3 0 4 0 1 0 0 0 Tenemos que formar 5 + 3 - 1 = 7 parejas. Estos pares son: (7, 2), (7, 4), (7, 8), (1, 2), (3, 2), (5, 2), (6, 2) Todos tienen una suma única

Enfoque de fuerza bruta: podemos ejecutar un bucle en las matrices A y B para encontrar los primeros N + M-1 pares de sumas únicas e imprimir sus índices en el camino.< br>Para verificar si se ha utilizado una cantidad específica, creamos un diccionario Python Bool. Si el valor del diccionario para esta suma es Falso, significa que este es el nuevo valor de la suma. Si es verdadero, la cantidad ya se ha utilizado.

Código:

de colecciones importar defaultdict as dd


# Función para generar pares únicos de sumas

def pares_únicos():


# Python Bool Dictionary

d = dd ( bool )

ct = 0


# Para cada elemento A, busque

< código clase = "comentarios"> # suma única de un par en B. Ruptura

# ciclo después de N + M-1 pares

para i en rango (n):

for j en rango (m):

if (ct = = n + m - 1 ):

romper

sm = a [i] + b [j]

si (d [sm] = = < /código> Falso ):

d [sm] < /código> = Verdadero

ct < clase de código = "palabra clave"> + = 1

print (i, j)

n, m = 6 , 4

a = [ 6 , 4 , 3 , 5 < /código> , 8 , 2 ]

b = [ 3 , 5 < /código> , 4 , 2 ]


pares_únicos ()

Salida: 

0 0 0 1 0 2 0 3 1 0 1 3 2 3 4 1 4 2

Complejidad del tiempo: porque recorremos la matriz utilizando bucles, la complejidad del tiempo resulta ser O ().

Enfoque eficiente: cómo solo ordenaremos ambas matrices, primero podemos crear N pares de sumas únicas conectando todos los elementos de la matriz A con el primer elemento de la matriz B, y luego conectando el resto M — 1 elementos del arreglo B con el último elemento del arreglo A.

Código:

de colecciones import defaultdict as dd


# Función para generar pares únicos de sumas

def unique_pairs_sort():


# Python Int Dictionary

< código clase="simple"> da = dd ( int )

db = dd ( int )


# Hacer un diccionario para almacenar el índice

f o i en rango (n):

da [a [i]] < clase de código ="palabra clave"> = i

para i en rango (m):

db [b [i]] = i

< / código>

# Ordenar arreglos

a.sort (); b.sort()


# N pares A con B [0]

para i en rango < clase de código = "simple"> (n):

print ( da [a [i] ], db [b [ 0 ]])

# M-1 empareja B con A [N-1]

para i en rango ( < código clase = "valor"> 1 , m):

< código clase = "funciones"> print (da [a [ - 1 ]], db [b [i]])

n, m = 6 , 4

a = [ < código clase ="valor "> 6 , 4 , 3 , 5 , < /código> 8 , 2 ]

b = [ 3 , 5 , 4 , 2 ]


unique_pairs_sort ()

Salida:

5 3 2 3 1 3 3 3 0 3 4 3 4 0 4 2 4 1

Complejidad temporal: La complejidad de esto es igual al tiempo que lleva ordenar: O (n Log n).
Complejidad espacial: porque estamos usando dos mapas/diccionarios diferentes para almacenar índices de matriz. La complejidad temporal será O (n + m), donde n — el tamaño de la primera matriz y m — el tamaño de la segunda matriz.