1

什么

我编写了一小段代码来查找和删除整数数组中是否存在重复数字。为此，我使用了 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();

    }

我的困难

我需要知道如何为这段编写的一小段代码找到时间复杂度，以及如果可能的话如何优化它。

我试过什么

我已经在互联网上阅读了一些关于如何计算算法的时间和空间复杂度的文章，下面是我认为的答案，但由于我是新手，我认为与其做出错误的假设，不如这样做会更好就此请教一些专家。

以下是我尝试过的。

列表更正列表 = 新列表（）；--> 这将执行 1 次

诠释我=0；-->这将执行1次

int i < input.Length --> 这将被执行 N 次

i++ --> 这将被执行 N 次

if (!correctedList.Contains(input[i])) --> 这可能会被执行 N 次

更正列表。添加（输入 [i]）；--> 这可能会被执行 N 次

因此，操作总数 = 1 + 1 + N + N + N + N = 4N+2

这等于 O(N) 吗？

我计算时间复杂度的方法是否正确？

预先感谢

4

1 回答 1

4

如果您调用的所有操作本身都是 O(1)，那将是 O(N)。列表中的包含不太可能是 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) 进行排序，然后扫描重复项。

于 2012-06-17T17:01:04.143 回答