計算時間和空間複雜度來刪除重複項

Question

什麼

我已經寫了一小段代碼，找到並刪除如果一個整數數組任何重複的號碼。我爲此使用了List。

守則

static int[] RemoveDuplicate(int[] input) 
    { 
     List<int> correctedList = new List<int>(); 

     for(int i = 0; i < input.Length; i++) 
     { 
      if (!correctedList.Contains(input[i])) 
      { 
       correctedList.Add(input[i]); 
      } 
      else 
      { 
       //skip 
      } 
     } 

     return correctedList.ToArray(); 

    } 

我的難處

我需要知道如何找到時間複雜度爲這個寫一小段代碼，如果可能的話如何優化它。

我有什麼企圖

我也做了互聯網上關於如何計算時間和空間的算法的複雜性，下面就一些閱讀是什麼，我覺得就是答案，但因爲我是新來的這個我認爲，而不是去錯誤的假設，最好諮詢一些專家。

下面是我的嘗試。

列表correctedList =新列表（）; - >這將被執行1次

INT I = 0; - >這將被執行1次

INT I < input.Length - >這將被執行N次

我++！ - >這將被執行N次

如果（correctedList 。載（輸入[1]）） - >這可被執行N次

correctedList.Add（輸入[1]）; - >這可被執行N次

所以，操作的總數目= 1 + 1 + N + N + N + N = 4N + 2

這是等於O（N）？

，是我的計算時間複雜度正確的方法是什麼？

預先感謝

Answer 1

這將是O（N），如果所有你打過電話的操作本身也是O（1）。列表中的Contains不太可能是O（1）。一般來說，在數組中搜索是O（N），這意味着你的算法是O（N^2）（我認爲是這樣）。

優化選項： 1）你可能做的最好的是O（N），但這意味着你需要一個包含O（1）的函數。你可以用散列表（或散列集）來做到這一點。散列表有O（1）插入和刪除。

2）您可以插入維護排序順序的結構（例如平衡樹）。插入將爲O（log N），解決方案的整體性能爲O（N log N）。

3）可能最常見也是最簡單的算法是對數組O（N log N）進行排序，然後掃描重複數據。