Trova se un array è una sequenza nel tempo O (n) e nello spazio O (1)

Question

Dato un array che potrebbe contenere duplicati, Come possiamo trovare se si tratta di una sequenza?

Es. {7, 3, 5, 4, 6, 2}

è una sequenza 2, 3, 4, 5, 6, 7

ordinamento è una soluzione ovvia. Come possiamo farlo nel tempo O (n) e nello spazio O (1)?

Answer 1

Che il mio tentativo:

1. Determinare min e max – O (n)
2. creare un array di valori Null della dimensione della matrice originale – O (n) (Sì, manca lo spazio requisito qui)
3. Iterate sull'array originale (O (n)) e inserite il numero che trovate all'indice (numero - min), se trovate un valore lì, non avete una sequenza, se vieni ad un fine e nessuna posizione è stata rivendicata, si ha una sequenza

public bool IsSequence(int[] values) 
{ 
    var min = values[0]; 
    var max = values[0]; 
    foreach (var value in values) 
    { 
     min = min > value ? value : min; 
     max = max > value ? max : value; 
    } 

    if ((max - min + 1) != values.Length) 
     return false; 

    var testingArray = new int?[values.Length]; 
    foreach (var value in values) 
    { 
     var index = value - min; 
     if (testingArray[index].HasValue) 
      return false; 
     else 
      testingArray[index] = value; 
    } 
    return true; 
} 

Answer 2

assumendo 1,2,3,3,4,1 è una sequenza indifferenziati valido e 2,4,6,8 è una sequenza valida (di passaggio due) pure, ma non è 1,3,5,9 (7 manca) e assumendo la matrice di ingresso possono essere sovrascritti,

1. determinare il massimo e il minimo: O (n) tempo, O (1) spazio. Puoi usare la prima e l'ultima posizione dell'array per questo.
2. determinare il passaggio. Il passo è il moltiplicatore meno comune di tutti a_n - min
3. se sono troppo distanti (max - min > (count + 1) * step), non può essere una sequenza. Altrimenti,
4. esegui un ordinamento intero in loco. Fino all'inizio> fine:
   • guardare la prima posizione. Lasciate che il valore non sia v_0
   • lasciare la sua posizione di destinazione quando non ci assumiamo alcuna duplicati ((v_0 - min)/step + start) siano i
     • se la posizione di destinazione è inferiore a start, si tratta di un duplicato. Spostalo sul retro e decrementa il puntatore finale
     • se la posizione di destinazione è maggiore di end, manca un elemento nella sequenza. Richiedi che l'array non è una sequenza.
   • se l'elemento è nella posizione di destinazione, incrementa il puntatore avviamento e il riferimento min
   • altrimenti se l'elemento nella posizione di destinazione è inferiore al riferimento minimo o uguale a v_0, sostituirlo alla fine dell'array e decrementa il puntatore finale. È un duplicato.
   • altrimenti scambiare l'elemento nella posizione di destinazione con v_0.
5. rivendicazione dell'array una sequenza

Il sul posto intero sort è O (n).In ogni passaggio uno:

• accorcia la matrice di ingresso e mantiene tutti gli elementi ordinati alle loro posizioni di destinazione o
• genere uno o due elementi precedentemente non smistata alla loro posizione finale.

Alla fine dell'ordinamento, ogni elemento è un duplicato nel blocco duplicato o nella posizione corretta nel blocco ordinato.

Si noti che il passaggio n. 3 può essere escluso. # 4 determinerà correttamente che questa non è una sequenza, anche se più lenta.

Se il passo deve essere 1, allora questo algoritmo può essere semplificata leggermente (vedi revisione # 1)

Answer 3

Questo algoritmo (Python) distrugge la matrice originale, ma altrimenti soddisfa O (n) e O (1) spazio extra.

# INPUT: An array 'arr' of N integers. 
# OUTPUT: If the array consists exactly of the integers 
#   S, S+1, ..., S+N-1, for some S, in any order, 
#   then modifies 'arr' into a sorted array and returns it. 
#   Otherwise, returns False, and 'arr' may have been modified. 
def sort_sequence (arr): 
    the_min = min(arr) 
    the_max = max(arr) 
    if the_max - the_min != len(arr) - 1: 
     return False 
    for i in range(len(arr)): 
     arr[i] -= the_min 
    for i in range(len(arr)): 
     while arr[i] != i: 
      j = arr[i] 
      t = arr[j] 
      if t == j: 
       return False 
      arr[j] = j 
      arr[i] = t 
    for i in range(len(arr)): 
     arr[i] += the_min 
    return arr 

Non ho ancora dimostrato formalmente che funzioni.

Perché questo è O (n)? Nell'ultimo anello doppio, dopo che un elemento è stato posto per la prima volta nel punto giusto, può essere visitato solo un'altra volta - o all'inizio di un altro ciclo interno dove è visto nel punto giusto, o dove è stato trovato essere nel modo di un elemento duplicato (la parte if t == h).