Encuentre un par de elementos de matriz con una suma y producto dados en O (n * log (n))

Question

Sea A una matriz de n enteros positivos, y k un entero dado.

Estoy buscando un algoritmo para encontrar si hay un par de elementos en la matriz tal que A[i] * A[j] == k y A[i] == A[j] + k. Si existe tal par, el algoritmo debería devolver su índice.

Este es un ejercicio de tarea, y nos dicen que hay una solución O (n * log (n)).

Answer 1

Aquí se aclara un poco la solución de gráficos noob.

Además, es más como O (N) (suponiendo que hashing no nos fallará), no O (N * log (N)).

Result findMultiplicationIndices(int[] A, int[] B, int k) 
{ 
    HashMap<Integer,Integer> aDivisors = new HashMap<Integer,Integer>(); 
    for(int i=0;i<A.length;i++) 
    { 
     int a = A[i]; 
     if(a!=0) 
     { 
      int d = k/a; 
      if(d*a == k) 
       aDivisors.put(d, i); 
     } 
    } 
    for(int i=0;i<B.length;i++) 
    { 
     Integer ai = aDivisors.get(B[i]); 
     if(ai != null) 
      return new Result(ai, i); 
    } 
    return null; 
} 

Answer 2

uso nlog (n) para ordenar
entonces itterate través de la matriz
para cada índice i calcular qué A [j] tendría que ser el fin de que la ecuación para estar satisfecho
comprobación para ver si theres tales un valor de la matriz

O (nlogn) + O (N) * O (log n)
= O (nlogn)

Answer 3

Sort the array. Also build a permuted index array by initializing an auxiliary array to 0, 1, 2 ... n and swapping indices every time you swap elements in the array, Time O(nLog(n)) 

for each element a[i] in array, Time O(n) 

    Binary Search for (a) k/a[i] or (b) a[i] - k, if found, return index j from permuted index array, Time O(log(n)) 

Answer 4

lo primero de la parte superior de la cabeza:

Make a Map<Integer, Integer> 

for each number a in A: 
    if (k/a) is a key in the HashMap: 
     output the index of a, and HashMap.get(k/a) 
    else 
     HashMap.add(a, indexof(a)) 

Así que es O (n) para atravesar la matriz, y O (log n) para buscar la llave en el mapa (suponiendo que utilizó un TreeMap, un HashMap podría ser mejor en el mejor de los casos, pero peor en el peor de los casos)

Editar: supongo que sólo respuestas a), pero se entiende la idea

Answer 5

Si k es fijo, entonces hay un número finito de enteros x, y tal que x * y = k. Para cada factor (x, y), recorra la lista para encontrar si A [i] = xo A [i] = y. Tiempo total de ejecución = O (n) * # factores de k = O (n) (determinísticamente, no suposiciones sobre hash)

El problema indica que A [i] son ​​todos positivos, por lo que k puede descomponerse x + y = k en finitas muchas formas también, así que O (n) también.