查找一個數組是否是O（n）時間和O（1）空間的序列

Question

給定一個可能包含重複數組的數組，我們如何才能找到它是否是一個序列？

例如， {7, 3, 5, 4, 6, 2}

是序列2, 3, 4, 5, 6, 7

排序是一個明顯的解決方案。我們如何在O（n）時間和O（1）空間中做到這一點？

Answer 1

讓我嘗試：

1. 確定最小和最大–爲O（n）
2. 使原始陣列–爲O（n）（是的，缺少空間要求的大小可爲空值的數組在這裏）
3. 迭代原始數組（O（n））並將您在索引處找到的數字（number - min），如果您在那裏找到一個值，您沒有序列，如果您來到結束和沒有位置被要求，你有一個序列

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

假設1,2,3,3,4,1是一個有效的未排序的序列和2,4,6,8是一個有效的序列（步驟2），以及，但1,3,5,9不是（7丟失），並假設輸入數組可以被覆蓋，

1. 確定最大值和最小值：O（n）時間，O（1）空間。你可以使用這個數組的第一個和最後一個位置。
2. 確定步驟。如果它們相距太遠（max - min > (count + 1) * step），則這個步驟是所有的最小公倍數乘數，這不能是一個序列。否則，
3. 做一個就地整數排序。直到開始>結束：
   • 看看第一個位置。讓那裏的價值是v_0
   • 讓其目標位置時，我們假定沒有重複（(v_0 - min)/step + start）是i
     • 如果目標位置小於start，這是一個重複的。如果目標位置超過end，某些元素在序列中缺失，請將其移動到後面並遞減結束指針
     • 。聲明該數組不是一個序列。
   • 如果元素是在目標位置處，遞增開始指針和min參考
   • 否則，如果在所述目標位置處的元素是小於參考最小或等於v_0，它交換到結束數組並減少結束指針。這是重複的。
   • 否則將目標位置的元素與v_0交換。
4. 權利要求所述陣列序列

在就地整數排序爲O（n）。在每個步驟中，要麼：

• 縮短輸入陣列和保持在它們的目標位置的所有排序元件或
• 排序一個或兩個先前未分類的元件到其目標位置。

在排序結束時，每個元素可以是重複塊中的副本，也可以是排序塊中的正確位置。

請注意，第3步可以省略。 ＃4會正確確定這不是一個序列，雖然速度較慢。

如果步驟必須是1，則該算法可被略微簡化（見版本＃1）

Answer 3

該算法（Python）的破壞原始陣列，但在其他方面滿足O（n）的時間和O（ 1）額外的空間。

# 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 

我還沒有正式證明它的工作原理。

爲什麼這是O（n）？在最後一個雙重循環中，一個元素首次放入正確的位置後，只能再次訪問它 - 無論是在另一個內部循環的開始，它看起來是在正確的位置，還是在它的位置妨礙重複元素（if t == h部分）。