移動元素移除重複項的複雜性

Question

以下代碼嘗試通過覆蓋重複元素來移除排序數組中的重複項。雖然它嵌套for循環，但其複雜度肯定小於O（n^2）。以下代碼的複雜程度如何？

int n = arr.length; 
    for(int i=0;i<n;i++){ 

     if(arr[i]==arr[i+1]){ 
      for(int j=i+1;j<n-1;j++){ 
       arr[j]=arr[j+1]; 
      } 
      n--; i--; 
     } 
    } 

Answer 1

讓我們從第一個位置開始。它肯定不會重複，所以你不會做任何動作。然後我們轉向第二個位置。它可以從第一個位置值複製，然後它可能不是。如果是的話，那麼你必須將它移動到最後，所以，對於前兩個位置，你有兩種情況，一種只是在數組中移動（它不是重複的），第二種是將元素移動到數組的末尾，需要n-2作業arr[j]=arr[j+1]。

現在，如果我們將第三個值移到第二個位置，我們仍然在（i--部分）。它可以是第一個值的複製，也可能不是。對於第一個選項，您必須採取n-3（因爲您做了n--，所以您將其從2的位置移動到位置n-1）操作arr[j]=arr[j+1]。現在，如果第二個值不是第一個值的重複（因此您沒有執行i--和n--），但是第三個值是前兩個值中的一個的副本，您仍然必須執行n-3操作arr[j]=arr[j+1]（從位置3到位置n）。所以，每種情況下的操作數量都保持不變。

所以，我們在這裏有一個模式：n-2 + n-3 + n -4 + ... + 3 + 2 + 1移動的東西。該總和是：

n-2 + n-3 + n -4 + ... + 3 + 2 + 1 = n(n+1)/2 - n - n + 1 

因此，基於此，由於第一部分是通過陣列，這是O(n)，該算法的複雜度是O(n^2)移動。最糟糕的情況是在數組中有所有相同的值。現在

，有一個更好的辦法。將所有值都放入Set。這需要移動數組（O(n)），然後檢查Set中是否有內容，即O(1)。然後從Set獲取所有結果，並將它們放在數組中，即O(n)。所以，這種算法的複雜性是O(n)。