Dada una matriz entera y un número constante X, imprima todos los pares de números en la matriz cuyo producto es igual a X. Seguimiento: ¿cómo lo hará en O (n)? ¿Cómo manejarás los pares duplicados?

El requisito es encontrar un número adecuado para cualquier otro número. Podemos usar un Hash Map ya que las búsquedas no son costosas, O (1).

Digamos que la matriz dada es A y el producto deseado es X.

Mientras (iterar a través del índice i)
{
If (X% A [i] == 0 Y ExistInHashMap (HashMap, X / A [i])
{
print (i + “Y” + ValFromHashMap (HashMap, X / A [i]));
}
PutInHash (HashMap, A [i], i) // par de valores clave con clave como valor de matriz
}

Esta solución es O (N) porque realiza operaciones O (1) sobre N elementos.

Para evitar duplicados por valor, solo puede imprimir un valor de la tabla hash.

Usaremos la clasificación de cubo para la complejidad de tiempo O (N).

Para N números, la complejidad temporal será O (N)
* Suponiendo que N no es muy grande de modo que la memoria no se vea comprometida.

Una vez que se realiza la clasificación, simplemente atraviese la matriz ordenada, para cada número dividir X por ese número y si el número resultante está presente en la matriz (Use la Búsqueda Binaria para calcular la complejidad del Tiempo O (log N) imprima los dos números más continúe.

Todo se puede hacer en O (N)

Esto se puede hacer en O (n) usando hashmap.

Por ejemplo, consideremos que los elementos de la matriz son {5, 10, 3, 25, 2, 11, 17} y el producto es 50. Tenemos que encontrar todos los pares en la matriz que da 50 como producto.

Aquí las combinaciones son (5,10), (10,5), (25,2), (2,25). Veamos cómo podemos encontrar estas combinaciones en O (n) usando hashmap.

Use hashmap para almacenar los elementos de la matriz con su valor de cociente de respuesta dividiendo el valor del producto con el elemento de la matriz.
Por lo tanto, los valores de hashmap son:

10.0 = 5
5.0 = 10
16.666666 = 3
2.0 = 25
2.9411764 = 17
25.0 = 2
4.5454545 = 11

Ahora verifique si los elementos de la matriz están presentes en las claves de hashmap. Si es así, esas son las combinaciones que estamos buscando.

De nuestra matriz, 5,10,25,2 son los elementos que contiene la clave hashmap.

Para evitar pares duplicados, simplemente elimine la clave del hashmap, que es el valor de otra combinación de teclas, que encontramos anteriormente. Por ejemplo, (5,10) es la combinación, que obtuvimos primero. Ahora elimine la clave 10 del hashmap.

Aquí está mi código en Java:

package com.arun.twoproduct; import java.util.HashMap;
import java.util.Map; public class TwoProduct { public static void main(String[] args) { int[] arr = { 5, 10, 3, 25, 2, 11, 17 };
int product = 50;
findTwoProduct(arr, product); } private static void findTwoProduct(int[] arr, int product) {
HashMap map = new HashMap<>();
for (int i : arr) {
float val = (float) product / i;
map.put(val, i);
}
for (int i = 0; i < arr.length; i++) { if (map.containsKey((float) arr[i])) {
float toDelete = map.get((float) arr[i]);
System.out.println(arr[i] + "," + map.get((float) arr[i]) + " ");
map.remove(toDelete);
}
}
} }


package com.arun.twoproduct; import java.util.HashMap;
import java.util.Map; public class TwoProduct { public static void main(String[] args) { int[] arr = { 5, 10, 3, 25, 2, 11, 17 };
int product = 50;
findTwoProduct(arr, product); } private static void findTwoProduct(int[] arr, int product) {
HashMap map = new HashMap<>();
for (int i : arr) {
float val = (float) product / i;
map.put(val, i);
}
for (int i = 0; i < arr.length; i++) { if (map.containsKey((float) arr[i])) {
float toDelete = map.get((float) arr[i]);
System.out.println(arr[i] + "," + map.get((float) arr[i]) + " ");
map.remove(toDelete);
}
}
} }


package com.arun.twoproduct; import java.util.HashMap;
import java.util.Map; public class TwoProduct { public static void main(String[] args) { int[] arr = { 5, 10, 3, 25, 2, 11, 17 };
int product = 50;
findTwoProduct(arr, product); } private static void findTwoProduct(int[] arr, int product) {
HashMap map = new HashMap<>();
for (int i : arr) {
float val = (float) product / i;
map.put(val, i);
}
for (int i = 0; i < arr.length; i++) { if (map.containsKey((float) arr[i])) {
float toDelete = map.get((float) arr[i]);
System.out.println(arr[i] + "," + map.get((float) arr[i]) + " ");
map.remove(toDelete);
}
}
} }


package com.arun.twoproduct; import java.util.HashMap;
import java.util.Map; public class TwoProduct { public static void main(String[] args) { int[] arr = { 5, 10, 3, 25, 2, 11, 17 };
int product = 50;
findTwoProduct(arr, product); } private static void findTwoProduct(int[] arr, int product) {
HashMap map = new HashMap<>();
for (int i : arr) {
float val = (float) product / i;
map.put(val, i);
}
for (int i = 0; i < arr.length; i++) { if (map.containsKey((float) arr[i])) {
float toDelete = map.get((float) arr[i]);
System.out.println(arr[i] + "," + map.get((float) arr[i]) + " ");
map.remove(toDelete);
}
}
} }


package com.arun.twoproduct; import java.util.HashMap;
import java.util.Map; public class TwoProduct { public static void main(String[] args) { int[] arr = { 5, 10, 3, 25, 2, 11, 17 };
int product = 50;
findTwoProduct(arr, product); } private static void findTwoProduct(int[] arr, int product) {
HashMap map = new HashMap<>();
for (int i : arr) {
float val = (float) product / i;
map.put(val, i);
}
for (int i = 0; i < arr.length; i++) { if (map.containsKey((float) arr[i])) {
float toDelete = map.get((float) arr[i]);
System.out.println(arr[i] + "," + map.get((float) arr[i]) + " ");
map.remove(toDelete);
}
}
} }


package com.arun.twoproduct; import java.util.HashMap;
import java.util.Map; public class TwoProduct { public static void main(String[] args) { int[] arr = { 5, 10, 3, 25, 2, 11, 17 };
int product = 50;
findTwoProduct(arr, product); } private static void findTwoProduct(int[] arr, int product) {
HashMap map = new HashMap<>();
for (int i : arr) {
float val = (float) product / i;
map.put(val, i);
}
for (int i = 0; i < arr.length; i++) { if (map.containsKey((float) arr[i])) {
float toDelete = map.get((float) arr[i]);
System.out.println(arr[i] + "," + map.get((float) arr[i]) + " ");
map.remove(toDelete);
}
}
} }


package com.arun.twoproduct; import java.util.HashMap;
import java.util.Map; public class TwoProduct { public static void main(String[] args) { int[] arr = { 5, 10, 3, 25, 2, 11, 17 };
int product = 50;
findTwoProduct(arr, product); } private static void findTwoProduct(int[] arr, int product) {
HashMap map = new HashMap<>();
for (int i : arr) {
float val = (float) product / i;
map.put(val, i);
}
for (int i = 0; i < arr.length; i++) { if (map.containsKey((float) arr[i])) {
float toDelete = map.get((float) arr[i]);
System.out.println(arr[i] + "," + map.get((float) arr[i]) + " ");
map.remove(toDelete);
}
}
} }


package com.arun.twoproduct; import java.util.HashMap;
import java.util.Map; public class TwoProduct { public static void main(String[] args) { int[] arr = { 5, 10, 3, 25, 2, 11, 17 };
int product = 50;
findTwoProduct(arr, product); } private static void findTwoProduct(int[] arr, int product) {
HashMap map = new HashMap<>();
for (int i : arr) {
float val = (float) product / i;
map.put(val, i);
}
for (int i = 0; i < arr.length; i++) { if (map.containsKey((float) arr[i])) {
float toDelete = map.get((float) arr[i]);
System.out.println(arr[i] + "," + map.get((float) arr[i]) + " ");
map.remove(toDelete);
}
}
} }


package com.arun.twoproduct; import java.util.HashMap;
import java.util.Map; public class TwoProduct { public static void main(String[] args) { int[] arr = { 5, 10, 3, 25, 2, 11, 17 };
int product = 50;
findTwoProduct(arr, product); } private static void findTwoProduct(int[] arr, int product) {
HashMap map = new HashMap<>();
for (int i : arr) {
float val = (float) product / i;
map.put(val, i);
}
for (int i = 0; i < arr.length; i++) { if (map.containsKey((float) arr[i])) {
float toDelete = map.get((float) arr[i]);
System.out.println(arr[i] + "," + map.get((float) arr[i]) + " ");
map.remove(toDelete);
}
}
} }


Bien. Se puede hacer con HashSet en Java ya que Set es una implementación efectiva para manejar duplicados.

Aquí vamos..

pares de productos de clase pública {

public static void main (String [] args) {
printProductPairs (nuevo int [] {5, 10, 3, 25, 2, 11, 17}, 50);
}

private static void printProductPairs (int [] array, int value) {
Establezca hashSet = new HashSet ();
int pairElement = 0;
para (elemento int: matriz) {
if (valor% elemento == 0) {
hashSet.add (elemento);
}
}

for (Elemento entero: hashSet) {
pairElement = valor / elemento;
if (hashSet.contains (pairElement)) {
System.out.println (elemento + “,” + pairElement);
}
}

}

}