面试 - 编写程序以删除偶数元素

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(输入)成正比.

他说:嗯...这意味着我需要等待更长时间才能获得结果,当输入大小增加时,我是对的吗？ Yes sirr you are

为我调整,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)的最终复杂度.

Answer 2

让我们这样想：

您正在执行的删除操作的数量强制为数组长度的一半（如果元素存储在数组中）。所以复杂度至少是 O(N) 。

您收到的问题让我假设您的教授希望您推理存储数字的不同方式。

通常，当您具有日志复杂性时，您会使用不同的结构，例如图形或树。

我能想到的对数复杂度的唯一方法是将数字存储在树中（有序树，b树......我们可以对此进行详细说明），但它实际上超出了考试的限制（将数字存储在大批）。

这对你来说有意义吗？