controllare se esiste un [i] = 2 * a [j] in un array non ordinato a?

Question

Data una sequenza non ordinata di [1, ..., n] di interi, fornire un algoritmo di runtime O (nlogn) per verificare che ci siano due indici i e j tali che a [i] = 2 * a [j] . L'algoritmo dovrebbe restituire i = 0 e j = 2 sull'input 4,12,8,10 e false sull'ingresso 4,3,1,11.

Penso che dobbiamo comunque ordinare l'array che è O (nlogn). Non sono sicuro di cosa fare dopo.

Answer 1

Hai ragione, il primo passo è l'ordinamento dell'array.

Dopo aver ordinato l'array, è possibile scoprire se un determinato elemento si trova all'interno dell'array nel tempo O(log n). Quindi, se per ciascuno degli elementi n, si verifica l'inclusione di un altro elemento nel tempo O(log n), si finisce con un runtime di O(n log n).

Questo ti aiuta?

Answer 2

1. creare una matrice di coppie A = {(a [0], 0), (un [1], 1), ..., (a [n-1], n-1)}
2. Sort A,
3. Per ogni (a [i], i) in A, eseguire una ricerca binaria per verificare se esiste una coppia (a [i] * 2, j) o meno. Possiamo farlo, perché A è ordinato.

Il passaggio 1 è O (n), mentre i passaggi 2 e 3 sono O (n * log n).

Inoltre, è possibile eseguire il passaggio 3 in O (n) (non è necessario eseguire la ricerca binaria). Perché se l'elemento corrispondente per A [i] è A [j], allora l'elemento corrispondente per A [i + 1] non può essere in A [0..j-1]. Quindi possiamo tenere due puntatori e trovare la risposta in O (n). Ma comunque, l'intero algoritmo sarà O (n log n) perché continuiamo a fare l'ordinamento.

Answer 3

L'ordinamento dell'array è una buona opzione - O (nlogn), assumendo che non si disponga di qualche opzione di ordinamento benna.

Una volta che è ordinato, è necessario passare solo attraverso la matrice due volte - credo che questo è O (n)

creare un elenco di 'doppie' che inizia vuota.

Quindi, per ogni elemento dell'array:

• controllo l'elemento contro il primo elemento della lista il 'doppio'
  • se è lo stesso, si vince
  • se l'elemento è più elevato, fosso il primo elemento della lista il 'doppio' e controllare di nuovo

• aggiungere il suo doppio alla fine della lista dei 'raddoppia'

• continuare fino a trovare un doppio o arrivare alla fine del primo elenco.

Answer 4

1. ordinare l'array (O(n log n), o O(n) se siete disposti ad allungare un punto su array di interi di dimensione fissa)
2. inizializzazione due puntatori ("veloce" e "lento") a l'inizio della matrice (O(1))
3. ripetutamente:
   1. incremento "veloce" fino a trovare un valore pari> = doppio del valore a "lento"
   2. se il valore in "fast" i è esattamente il doppio del valore a "lento", restituire true
   3. incremento "lento" fino a trovare un valore> = la metà del valore in fast
   4. se il valore a "lento" è esattamente la metà del valore in "fast" , restituiscono vero
4. se uno dei tentativi per incrementare va oltre la fine, return false

Poiché ciascuno dei fast e slow può essere incrementata al massimo n volte in totale prima di raggiungere la fine della matrice , il "ripetutamente" parte è O(n).

Answer 5

Nota: che può essere fatto su O(n) in media, utilizzando un hash table.

set <- new hash set 
for each x in array: 
    set.add(2*x) 
for each x in array: 
    if set.contains(x): 
     return true 
return false 

Prova:
=>
Se ci sono 2 elementi a[i] e a[j] tale che a[i] = 2 * a[j], allora quando l'iterazione prima volta, abbiamo inserito 2*a[j] al set quando si legge a[j]. Nella seconda iterazione, troviamo che a[i] == 2* a[j] è impostato e restituisce true.

< =
Se l'algoritmo restituito vero, allora trovato a[i] tale che a[i] è già nel set di seconda iterazione. Quindi, durante la prima iterazione, abbiamo inserito a[i]. Questo può essere fatto solo se esiste un secondo elemento a[j] tale che a[i] == 2 * a[j] e abbiamo inserito a[i] durante la lettura di a[j].

Nota:
Per riportare gli indici dei elemets, si può semplicemente utilizzare un hash-map invece di un insieme, e per ogni i archivio 2*a[i] come chiave e i come valore.

Esempio:
Input = [4,12,8,10]

primo inserto per ogni x - 2x alla tabella hash, e l'indice.Otterrete:

hashTable = {(8,0),(24,1),(16,2),(20,3)}

Ora, sulla iterazione secondo articolo di controllare per ogni elemento se è nella tabella:

arr[0]: 4 is not in the table 
arr[1]: 12 is not in the table 
arr[2]: 8 is in the table - return the current index [2] and the value of 8 in the map, which is 0. 

modo, l'uscita finale è 2,0 - come previsto.

---

(1) Complessità avviso:
Qui, O(n) assume O(1) funzione di hash. Questo non è sempre vero. Se assumiamo la funzione di hash O(1), possiamo anche supporre che l'ordinamento con radix-sort sia O(n), e usando una post-elaborazione di O(n) [simile a quella suggerita da @SteveJessop nella sua risposta], possiamo anche ottenere O(n) con smistamento- algoritmo basato.

Answer 6

È inoltre possibile utilizzare un albero bilanciato, ma utilizza uno spazio aggiuntivo ma non danneggia la matrice.

A partire da i=0 e incrementando i, inserire elementi, controllando se due o metà dell'elemento corrente è già presente nell'albero.

Un vantaggio è che funzionerà nel tempo O(M log M) dove M = min [max{i,j}]. Potresti potenzialmente modificare l'algoritmo basato sull'ordinamento per provare a fare O(M log M) ma potrebbe complicarsi.

proposito, se si utilizza solo il confronto, v'è un limite inferiore Omega(n log n), riducendo il problema elemento distinzione a questo:

duplicare l'array di input. Utilizzare l'algoritmo per questo problema due volte. Quindi, a meno che non porti nella tua foto roba di tipo hashing, non puoi ottenere un algoritmo migliore di Theta(n log n)!