Trova l'elemento con la distanza più lunga in un dato array in cui ogni elemento appare due volte?

Question

Dato un array di int, ogni int appare esattamente DUE nell'array . trova e restituisce int tale che questa coppia di int abbia la distanza massima tra tra di loro in questo array.

ad es. [2, 1, 1, 3, 2, 3]

2: d = 5-1 = 4; 
1: d = 3-2 = 1; 
3: d = 6-4 = 2; 
return 2 

Le mie idee:

Usa HashMap, chiave è il a[i], e il valore è l'indice. Scansiona il a[], metti ciascun numero in hash. Se un numero viene colpito due volte, usa il suo indice meno il vecchio indice numeri e usa il risultato per aggiornare il valore dell'elemento in hash.

Successivamente, scansionare l'hash e restituire la chiave con l'elemento più grande (distanza). è O (n) nel tempo e nello spazio.

Come farlo in tempo O (n) e O (1) spazio?

Answer 1

Si desidera avere la distanza massima, quindi presumo che il numero cercato sia più all'inizio e alla fine. Questo è il motivo per cui eseguirò un loop sull'array dall'inizio alla fine allo stesso tempo.

[2, 1, 1, 3, 2, 3] 
Check if 2 == 3? 
Store a map of numbers and position: [2 => 1, 3 => 6] 
Check if 1 or 2 is in [2 => 1, 3 => 6] ? 

Lo so, non è nemmeno pseudo codice e non completo ma solo per dare l'idea.

Answer 2

Impostare l'indice iLeft sul primo elemento, l'indice iRight sul secondo elemento. Incrementa l'indice iRight finché non trovi una copia dell'elemento sinistro o incontri la fine dell'array. Nel primo caso, ricorda la distanza.

Incremento iLeft. Inizia la ricerca dalla nuova iRight. Il valore iniziale di iRight non verrà mai diminuito. codice Delphi:

iLeft := 0; 
    iRight := 1; 

    while iRight < Len do begin //Len = array size 
    while (iRight < Len) and (A[iRight] <> A[iLeft]) do 
     Inc(iRight); //iRight++ 
    if iRight < Len then begin 
     BestNumber := A[iLeft]; 
     MaxDistance := iRight - iLeft; 
    end; 
    Inc(iLeft); //iLeft++ 
    iRight := iLeft + MaxDistance; 
    end; 

Answer 3

Questo algoritmo è O (1) spazio (con qualche imbroglio), O (n) (media), richiede la matrice di origine per essere non-const e distrugge alla fine. Inoltre limita i possibili valori nella matrice (tre bit di ciascun valore devono essere riservati all'algoritmo).

La metà della risposta è già nella domanda. Usa hashmap. Se un numero viene colpito due volte, usa la differenza indice, aggiorna il risultato migliore fino a quel momento e rimuovi questo numero dall'hashmap per liberare spazio. Per renderlo O (1) spazio, riutilizzare semplicemente l'array sorgente. Converti l'array in hashmap sul posto.

Prima di trasformare un elemento di matrice nella cella di hashmap, ricordarne il valore e la posizione. Dopo questo potrebbe essere sovrascritto in modo sicuro. Quindi utilizzare questo valore per calcolare una nuova posizione nella hashmap e sovrascriverla. Gli elementi vengono rimescolati in questo modo finché non viene trovata una cella vuota. Per continuare, seleziona qualsiasi elemento, che non è già riordinato. Quando tutto è riordinato, ogni coppia int è sicuramente colpita due volte, qui abbiamo una hashmap vuota e un valore di risultato migliore aggiornato.

Un bit riservato viene utilizzato durante la conversione di elementi di matrice nelle celle di hashmap. All'inizio è cancellato. Quando un valore viene riordinato alla cella hashmap, questo bit viene impostato. Se questo bit non è impostato per l'elemento sovrascritto, questo elemento è appena preso per essere elaborato successivamente. Se questo bit è impostato per la sovrascrittura dell'elemento, qui c'è un conflitto, selezionare il primo elemento non utilizzato (con questo bit non impostato) e sovrascriverlo.

2 altri bit riservati vengono utilizzati per concatenare valori in conflitto. Codificano le posizioni in cui la catena viene avviata/terminata/continuata. (Potrebbe essere possibile ottimizzare questo algoritmo in modo che siano necessari solo 2 bit riservati ...)

Una cella di hashmap deve contenere questi 3 bit riservati, l'indice del valore originale e alcune informazioni per identificare univocamente questo elemento. Per rendere ciò possibile, una funzione di hash dovrebbe essere reversibile in modo tale che parte del valore possa essere ripristinata data la sua posizione nella tabella. Nel caso più semplice, la funzione di hash è solo ceil(log(n)) bit meno significativi. Valore nella tabella è costituito da 3 campi:

• 3 bit riservati
• 32 - 3 - (ceil(log(n))) bit di ordine dal valore originario
• ceil(log(n)) bit per la posizione dell'elemento nell'array originale

Complessità è O (n) solo in media; la complessità peggiore è O (n^2).

Un'altra variante di questo algoritmo consiste nel trasformare sequenzialmente l'array in hashmap: su ogni passaggio m con 2^m primi elementi della matrice convertiti in hashmap. Alcuni array di dimensioni costanti possono essere intercalati con l'hashmap per migliorare le prestazioni quando m è basso. Quando m è alto, dovrebbero esserci abbastanza coppie int, che sono già state elaborate e che non richiedono più spazio.

Answer 4

Non c'è modo di farlo nel tempo O (n) e nello spazio O (1).