计算时间和空间复杂度来删除重复项

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）进行排序，然后扫描重复数据。