Trova se una coppia esiste in una matrice non ordinata?

Questo può essere fatto in O (nlogk) usando una struttura di ricerca bilanciata, in cui per ogni nodo si memorizza anche MIN (nodo) - il valore minimo nella sua sottostruttura, MAX (nodo) - il valore massimo nella sua sottostruttura e DIST (nodo): la differenza assoluta minima di qualsiasi coppia di valori nella relativa sottostruttura. Questi valori possono essere calcolati in modo ricorsivo utilizzando le seguenti equazioni:

MAX(node) = max{node->value, MAX(node->left), MAX(node->right)}
MIN(node) = min{node->value, MIN(node->left), MIN(node->right)}
DIST(node) = min{DIST(node->left), DIST(node->right),
                 |MAX(node->left) - (node->value)|,
                 |MIN(node->right) - (node->value)|}

Puoi aggiornare questi valori in O (log k) quando aggiorni l'albero, poiché devi solo aggiornarli sul percorso di ricerca.

Quindi puoi far scorrere una finestra di dimensione k sull'array e controllare se contiene la coppia richiesta usando l'albero come segue:

1. Inserisci i primi k elementi (0..k-1) dell'array nell'albero descritto sopra e imposta i = k.
2. Se DIST (nodo radice) < = X, restituisce True.
3. Se i > = n, restituisci False.
4. Rimuovere l'elemento (ik) -th dell'array dall'albero, aggiungere l'elemento i-es dell'array all'albero (durante l'aggiornamento di MIN, MAX e DIST dei nodi sui percorsi di inserimento / rimozione).
5. Aumenta di una unità e vai a 2.

Il passo 1 (costruire l'albero) richiede O (nlogk) e il passo 4 (l'aggiornamento dell'albero) richiede O (log k) e viene ripetuto O (n) volte.

Può essere fatto in tempo lineare previsto.

Mantieni una percentuale hashtable di H della forma [i*k, (i + 1)*k] a un intero che rientra in quell'intervallo. Poi:

H = HashTable();
for (i = 0; i < len(A); ++i) {
  bucket = A[i] / x;
  if (H.contains(bucket)) {
    return true; // Two elements in same bucket -> pair exists
  }
  if (H.contains(bucket - 1) && (A[i] - H[bucket - 1]) < x) {
    return true; // Element in previous bucket with right distance
  }
  if (H.contains(bucket + 1) && (H[bucket + 1] - A[i]) < x) {
    return true; // Element in next bucket with right distance
  }
  // Time to update H
  H[bucket] = A[i];
  if (i >= K) {
    H.remove(A[i - K] / x); // Remove old entry from H
  }
}
return false; // No pair found

Penso che tu possa fare fino a nlog (k). Pensaci in geometria. Per ogni punto si disegna un tunnel di valori avanzati corrispondenti ai criteri. Quindi per il punto successivo controlli le gallerie precedenti. Se ordinate i vostri tunnel in qualche modo dovreste essere in grado di effettuare il controllo senza iterarli tutti.