c# - 面试——写一个程序去掉偶数元素

Question

我今天被问到这个问题，我知道答案很简单，但他让我一直到最后。

问题

编写程序删除存储在 ArrayList 中的偶数，其中包含 1 - 100。

我只是说哇

给你，这就是我的实现方式。

ArrayList source = new ArrayList(100);
for (int i = 1; i < 100; i++)
{
    source.Add(i);
}


for (int i = 0; i < source.Count; i++)
{
    if (Convert.ToInt32(source[i]) % 2 ==0)
    {
        source.RemoveAt(i);
    }
}

//source contains only Odd elements

转折

他问我这个给他一个方程式的计算复杂度是多少。我只是说这是与 N(输入)成正比的线性关系。

他说:嗯……所以这意味着当输入大小增加时我需要等待更长的时间才能得到结果，对吗？ 是的，先生，您是

为我调整它，让它 Log(N) 尽可能多地尝试他说的。我在这部分失败得很惨。

• 因此来到这里寻求正确的逻辑、答案或算法来执行此操作。

注意:他不需要 Linq，不需要额外的花里胡哨。只是简单的循环或其他逻辑来完成它

Answer 1

我敢说复杂度实际上是 O(N^2)，因为数组中的删除是 O(N) 并且可能会为每个项目调用它。

因此，遍历数组(列表)的时间复杂度为 O(N)，每次删除的时间复杂度为 O(N) => O(N) * O(N)。

既然不是很清楚，那我就说说道理吧。在每一步都可能会移除一个项目(假设最坏的情况是每个项目都必须被移除)。在数组中，删除是通过移位完成的。因此，要删除第一项，我需要将以下所有 N-1 项向左移动一个位置:

1 2 3 4 5 6...
<---
2 3 4 5 6...

现在，在每次迭代中我都需要移位，所以我进行了 N-1 + N-2 + ... + 1 + 0 移位，结果为 (N) * (N-1)/2(算术级数)给出 O(N^2) 的最终复杂度。