Znajdź, czy tablica jest sekwencją w czasie O (n) i O (1)

Question

Biorąc pod uwagę tablicę, która może zawierać duplikaty, Jak możemy ustalić, czy jest to sekwencja?

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

jest sekwencją 2, 3, 4, 5, 6, 7

sortowania jest oczywiste rozwiązanie. Jak możemy to zrobić w czasie O (n) i O (1)?

Answer 1

Niech mój try:

1. Ustal min i max – O (n)
2. Złóż szereg pustych wartości wielkości oryginalnej tablicy – O (n) (Tak, brakuje zapotrzebowanie na miejsce tutaj)
3. Powtórz pierwotną tablicę (O (n)) i umieść numer, który znajdujesz w indeksie (liczba - min), jeśli znajdziesz tam wartość, nie masz sekwencji, jeśli dojdziesz do koniec i nie zgłoszono żadnej pozycji, masz sekwencję

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

zakładając 1,2,3,3,4,1 jest ważna kolejność sortowania i 2,4,6,8 jest ważna sekwencja (z drugim etapie) jak również, ale nie jest 1,3,5,9 (7 brak) i przy założeniu, że układ wejściowy może zostać zastąpiona,

1. określić maksymalne i minimalne: O (n) czas, O (1) spacja. Możesz użyć do tego pierwszej i ostatniej pozycji tablicy.
2. określić krok. Krok jest najmniej powszechnym mnożnikiem wszystkich wartości, jeśli są one zbyt oddalone (max - min > (count + 1) * step), nie może to być sekwencja. W przeciwnym razie należy wykonać sortowanie liczb całkowitych w miejscu. Do początku> końca:
   • Spójrz na pierwszą pozycję. Niech wartość być v_0
   • niech swoją pozycję docelową, gdy zakładamy żadnych duplikatów ((v_0 - min)/step + start) być i
     • jeśli pozycja docelowa jest mniej niż start, to duplikat. Przesuń go do tyłu i zmniejsz wskaźnik końcowy, jeśli pozycja docelowa jest większa niż end, brakuje jakiegoś elementu w sekwencji. Twierdzenie, że tablica nie jest sekwencją.
   • , gdy element znajduje się w położeniu docelowym zwiększyć wskaźnik początku i odniesienia min
   • innego, gdy element w położeniu docelową jest mniejsza niż minimalna odniesienia lub równa v_0, wymienić go na koniec tablicy i zmniejsz wskaźnik końcowy. To duplikat.
   • Zamień element w docelowej pozycji na v_0.
3. Zastrzeżenie tablica sekwencja

IN miejscu całkowitą rodzaj O (n).W każdym etapie, że albo:

• skraca szereg wejść i utrzymuje wszystkie elementy posortowane w ich położeniach docelowych lub
• rodzaju jedno lub dwa wcześniej nieposortowane elementów do ich położenia docelowego.

Po zakończeniu sortowania każdy element jest duplikatem w duplikacie bloku lub w poprawnej pozycji w posortowanym bloku.

Należy pamiętać, że krok 3 można pominąć. # 4 poprawnie określi, że nie jest to sekwencja, aczkolwiek wolniejsza.

Jeśli etap jest równy 1, to algorytm można uprościć nieco (patrz wersja # 1)

Answer 3

tego algorytmu (Python) niszczy oryginalnej tablicy, ale spełniająca O (n) oraz O (1) dodatkowa przestrzeń.

# 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 

Nie formalnie udowodniłem, że to działa.

Dlaczego to jest O (n)? W końcowej podwójnej pętli, po umieszczeniu elementu w jego właściwym miejscu, można go odwiedzać jeszcze tylko raz - albo na początku kolejnej pętli wewnętrznej, gdzie jest widoczne we właściwym miejscu, albo tam, gdzie jest znalezione być przeszkodą dla duplikatu (część if t == h).