In un tempo inferiore al lineare, trova il duplicato in un array ordinato

Question

Oggi un'intervistatore mi ha fatto questa domanda. La mia risposta immediata è stata che potevamo semplicemente fare una ricerca lineare, confrontando l'elemento corrente con l'elemento precedente nell'array. Poi mi ha chiesto come si potrebbe risolvere il problema in un tempo non lineare.

Ipotesi

• L'array è ordinato
• C'è solo uno duplicare
• La matrice è solo popolato con i numeri [0, n], dove n è la lunghezza del array.

Esempio matrice: [0,1,2,3,4,5,6,7,8,8,9]

ho tentato di trovare una divide et impera algoritmo per risolvere questo problema, ma non sono sicuro che sia stata la risposta giusta. Qualcuno ha qualche idea?

Answer 1

può essere fatto in O (log N) con una ricerca binaria modificata:

Inizio nel mezzo della matrice: Se array [idx] < IDX il duplicato è a sinistra, altrimenti a destra. Risciacqua e ripeti.

Answer 2

Ho tentato di elaborare un algoritmo di divisione e conquista per risolvere questo problema, ma non sono sicuro che fosse la risposta giusta.

Certo, si potrebbe fare una ricerca binaria.

Se arr[i/2] >= i/2 il duplicato si trova nella metà superiore dell'array, altrimenti si trova nella metà inferiore.

while (lower != upper) 
    mid = (lower + upper)/2 
    if (arr[mid] >= mid) 
     lower = mid 
    else 
     upper = mid-1 

Poiché la matrice tra lower e upper viene dimezzata ogni iterazione, l'algoritmo viene eseguito in O (log n).

ideone.com demo in Java

Answer 3

Se nessun numero è presente nella matrice, come nell'esempio, è fattibile in O (log n) con una ricerca binaria. Se a[i] < i, il duplicato è precedente a i, altrimenti è dopo i.

Se c'è un numero assente e uno duplicato, sappiamo ancora che se a[i] < i il duplicato deve essere prima i e se a[i] > i, il numero di assenti deve essere prima di i e il duplicato dopo. Tuttavia, se a[i] == i, non sappiamo se il numero mancante e il duplicato sono entrambi precedenti allo i o entrambi dopo i. In questo caso, non vedo un modo per un algoritmo sublineare.

Answer 4

L'array di esempio è leggermente diverso dalla domanda. Poiché n è la lunghezza dell'array e ci sono un solo duplicato nell'array, il valore di ogni elemento dell'array dovrebbe essere in [0, n-1].

Se questo è vero, allora questa domanda è la stessa con How to find a duplicate element in an array of shuffled consecutive integers?

Il seguente codice dovrebbe trovare il duplicato in O (n) e O (1) spazio.

public static int findOnlyDuplicateFromArray(int[] a, boolean startWithZero){ 
    int xor = 0; 
    int offset = 1; 
    for(int i=0; i < a.length; i++){ 
     if(startWithZero) 
      xor = xor^(a[i] + offset)^i; 
     else 
      xor = xor^a[i]^i; 
     } 
     if(startWithZero) 
      xor = xor - offset; 
    return xor; 
} 

Answer 5

Che ne dici? (Ricorsione stile)

public static int DuplicateBinaryFind(int[] arr, int left, int right) 
{ 
    int dup =0; 

    if(left==right) 
    { 
     dup = left; 
    } 
    else 
    { 
     int middle = (left+right)\2; 
     if(arr[middle]<middle) 
     { 
      dup = DuplicateBinaryFind(arr,left, middle-1); 

     } 
     else 
     { 
      dup = DuplicateBinaryFind(arr, middle+1, right); 
     } 
    } 

    return dup; 

} 

Answer 6

Differenza tra somma di determinati elementi di matrice e la somma di 0 a n-1 numeri naturali ti dà l'elemento duplicato. La somma di elementi da 0 a n-1 è (N * N-1)/2 esempio di matrice è [0,1,2,3,4,5,6,7,8,8,9] somma di 0 a 9 numeri naturali è: 45 somma di elementi di matrice dati: 53 53-45 = 8 Qual è l'elemento duplicato