Suchen Sie ein Paar Array-Elemente mit einer gegebenen Summe und einem Produkt in O (n * log (n))

Question

Sei A ein Array von n positiven ganzen Zahlen und k eine gegebene ganze Zahl.

Ich suche nach Algorithmus, um zu finden, ob es ein Paar von Elementen im Array gibt, so dass A[i] * A[j] == k und A[i] == A[j] + k. Wenn es ein solches Paar gibt, sollte der Algorithmus seinen Index zurückgeben.

Dies ist eine Hausaufgabe, und uns wird gesagt, dass es eine O (n * log (n)) Lösung gibt.

Answer 1

ist etwas Graphics Noob Lösung geklärt.

Auch ist es mehr wie O (N) (vorausgesetzt Hashing wird uns nicht scheitern), nicht 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

Verwendung nlog (n) zu sortieren
dann itterate durch das Array
für jeden Index i berechnen, was A [j] würde für die Gleichung, um sein müssen erfüllt sein
Prüfung, um zu sehen, ob noch solchen

ein Wert in dem Array

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

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

die erste, was aus der Spitze von dem Kopf:

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

So ist es O (n), um das Array zu durchqueren, und O (log n) den Schlüssel in der Karte zu sehen (vorausgesetzt, Sie eine TreeMap verwendet wird, könnte ein HashMap im besten Fall besser sein, aber schlechter in der schlimmste Fall)

Edit: ich denke, dass nur Antworten zu a), aber Sie bekommen die Idee hier

Answer 5

Wenn k fest ist, dann gibt es endlich viele ganze Zahlen x, y, so dass x * y = k. Durchlaufen Sie für jeden Faktor (x, y) die Liste, ob A [i] = x oder A [i] = y ist. Gesamtlaufzeit = O (n) * # Faktoren von k = O (n) (deterministisch, keine Annahmen über Hashing)

Das Problem besagt, dass A [i] alle positiv sind, also kann k x + zerlegt werden y = k auf endlich viele Arten, also auch O (n).