Trouver une paire d'éléments de tableau avec une somme et un produit donnés dans O (n * log (n))

Question

Soit A un tableau de n entiers positifs, et k un entier donné.

Je cherche algorithme pour trouver s'il y a une paire d'éléments dans le tableau tel que A[i] * A[j] == k et A[i] == A[j] + k. S'il existe une telle paire, l'algorithme doit retourner son index.

Ceci est un exercice de devoirs, et on nous dit qu'il existe une solution O (n * log (n)).

Answer 1

Voici quelque peu clarifié la solution de Graphics Noob. De plus, c'est plus comme O (N) (en supposant que le hachage ne nous manquera pas), pas 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

utilisation nlog (n) pour trier
itterate puis à travers le tableau
pour chaque indice i calculer ce que A [j] devrait être pour que l'équation soit satisfaite
vérifier pour voir s'il y a cette une valeur dans le tableau

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

chose d'abord le haut de ma tête:

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)) 

Il est donc O (n) pour traverser le tableau, et O (log n) pour rechercher la clé dans la carte (en supposant que vous utilisez un TreeMap, HashMap pourrait être mieux dans le meilleur des cas, mais pire le pire des cas)

Edit: Je suppose que les réponses seulement), mais vous avez l'idée

Answer 5

Si k est fixé, alors il y a un nombre fini d'entiers x, y tels que x * y = k. Pour chaque facteur (x, y), parcourez la liste en recherchant si A [i] = x ou A [i] = y. Temps d'exécution total = O (n) * # facteurs de k = O (n) (déterminisme, pas hypothèses sur le hachage)

Le problème indique que A [i] sont tous positifs, donc k peut être décomposé x + y = k de manière infiniment différente, donc O (n) aussi.