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

Question

我今天被问到这个问题，我知道答案非常简单，但他一直让我感到困惑。

问题

编写一个程序，从包含1-100的ArrayList中删除偶数。

我只能说哇

这就是我的实现方式。

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，也不要额外添加功能。只需使用简单的循环或其他逻辑即可完成。

- Deeptechtons

---

LINQ无法帮助，它只是将那些肮脏的工作藏在幕后。 - xandy

没关系。您不能使用LINQ来删除内容。而且，使用数组并不总是非常高效的。 - decyclone

由于结果是O(N)，而您删除了O(N)个元素，因此您无法获得比O(N)更好的结果。 - Daniel Fischer

他最可能想听到的是这种推理不可能 (:)，或者只是想看看你的方法或思考过程。 - Hari Menon

不算回答，但是使用两个整型数组且不需要装箱、转换或内部重定位才是真正优化该算法的方式……只是说说而已。 - Tim M.

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)。

- Tudor

---

我没有给你点踩，而且我也不喜欢点踩。但是删除是通过索引进行的，因此始终为1，而不是像你说的O（N）。 - Deeptechtons

你认为这个“通过索引删除”的操作是如何完成的？需要进行移位操作。假设我想删除第三个项目，那么第四、第五...第N项都需要向左移动一个位置。 - Tudor

请参阅 ArrayList.RemoteAt() 的文档。它的时间复杂度被记录为 O(n)：http://msdn.microsoft.com/en-us/library/system.collections.arraylist.removeat.aspx。 - shf301

跟踪下一个要插入值的索引。遍历数组。如果遇到偶数，就将其写入该索引并增加索引。如果遇到奇数，则不执行任何操作。你只需遍历一次，在此过程中，每个偶数要么不移动，要么移动一次，而奇数则不移动。这是O（N） - 当然，这并不是问题中所要求的O（log N）。 - Michael J. Barber

@MichaelJ.Barber，其他人都在谈论楼主的算法。 - Daniel Fischer

Answer 2

让我们这样考虑：

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

你收到的问题让我想到，你的教授希望你思考不同的存储数字的方式。

通常，当你具有对数复杂度时，你正在使用不同的数据结构，比如图形或树。

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

你觉得合理吗？

- Daniele B

---

@Daniele.B 当然可以。我应该给这个答案打分。但是我也要为其他人的技术点赞 :) - Deeptechtons

正如您所说，严格来说这个问题没有答案；因为问题说明输入是一个“arraylist”，由于它指定了这种类型限制，任何查找要删除的项目或基于有效值填充新列表的操作仍将是O(n/2)=O(n)，除非您可以通过无限数量的多个线程节省时间。 - Seph

Answer 3

如果您保留当前读取位置和当前写入位置的两个索引，可以显着提高性能。

int read = 0
int write = 0;

这个想法是read依次查看数组的每个成员；write跟踪列表的当前末尾。当我们找到要删除的成员时，我们将read向前移动，但不移动write。

for (int read = 0; read < source.Count; read++) {
  if (source[read] % 2 != 0) {
    source[write] = source[read];
    write += 1;
  }
}

最后，告诉ArrayList它的新长度是“write”的当前值。

这将把您从原始的O(n^2)降至O(n)。

（注意：我没有测试过这个方法）

- Iain

---

问题是：「编写一个程序，从包含1-100的ArrayList中删除偶数。」你误解了这个问题。 - Saeed Amiri

@SaeedAmiri 哎呀，你说得对，我搞反了。好发现。 - Iain

@SaeedAmiri 我真的不理解问题，也不知道Lain的代码哪里出错了。你能给我1-10的输入/输出吗？（以及Lain“错误”的代码的结果） - Viktor Lova

@nsinreal：点击“1小时前编辑”中的链接，您将看到Iain修复的错误。 - Steve Jessop

Answer 4

如果不改变数据结构或对ArrayList中的项目存储方式进行某些假设，我看不出如何避免检查每个成员的奇偶性（因此至少具有O(n)复杂度）。也许面试官只是想让你告诉他这是不可能的。

- Ohad Schneider

Answer 5

如果您有无限的并行线程可用，那么这是可能的IF。

假设我们有一个包含n个元素的数组。为每个元素分配一个线程。假设所有线程都完美同步。

1. 每个线程决定它的元素是偶数还是奇数。(时间复杂度为 O(1)。)
2. 确定数组中它下面有多少个奇数元素。(时间复杂度为 O(log(n))。)
   1. 在第二个数组中标记0或1，具体取决于在相同索引处是偶数还是奇数。因此，每个条目都是该位置的奇数计数。
   2. 如果您的索引是奇数，请添加前一个数字。现在，每个条目都是当前块中2个奇数的计数，直到您自己。
   3. 如果您的索引模4为2，请添加下面的值，如果为3，则添加下面2个索引的答案。现在，每个条目都是当前块中4个奇数的计数，直到您自己。
   4. 使用块大小为2 ** i的块继续此模式（如果您在顶部，则添加底部的计数）log2(n)次-现在此数组中的每个条目都是以下奇数的计数。
3. 每个CPU将其值插入正确的插槽中。
4. 将数组截断为正确的大小。

我愿意打赌，像这样的东西就是你的朋友心中所想的答案。

- btilly

---

@Deeptechtons - 你能回报一下你的朋友说了什么吗？我想知道我是否正确地揭示了他的作弊手段。 - btilly

嗨btilly，我还没有再次见到他。明天我会带着答案来 :) - Deeptechtons

Answer 6

如果你真的必须使用ArrayList并且需要主动删除条目（而不是一开始就不添加它们）

不要通过 i + 1 增加，而是通过 i + 2 增加将消除你检查是否为奇数的需求。

for (int i = source.Count - 1 ; i > 0; i = i i 2)
{
   source.RemoveAt(i);
}

编辑：我知道这只适用于source包含1-100的连续条目。

- Brunner

---

他的意思是删除偶数数字，而不是在偶数位置上。即使这样，它也不会改善整体复杂度。 - Tudor

那是真的，但他确实说它包含1-100，并且他添加它们的方式意味着它们是连续的。而且它比初始版本更加“调整”。 - Brunner

@Brunner 我觉得你没有理解重点。如果数组包含2、2、3、3、4、4，你需要删除第1、2、5和6个元素，这些元素都包含偶数。 - Adam Liss

@Brunner 这将被简化为 N/2，这是我建议的，但他坚持要用 log(N) :( - Deeptechtons

@AdamLiss 对我来说听起来这取决于实现方式，即没有重复项且按顺序添加。 - Brunner

@Deeptechtons 当涉及到调整这个东西时，这是我能想到的最好的方法。 - Brunner

Answer 7

给定解决方案的问题在于它从开头开始，因此每次删除一个项目时整个列表都必须被移动。

Initial List:       1, 2, 3, 4, 5, ..., 98, 99
                         /  /  /  ///  /
After 1st removal:  1, 3, 4, 5, ..., 98, 99, <empty>
                            /  ///  /   /
After 2nd removal:  1, 3, 5, ..., 98, 99, <empty>, <empty>

我使用斜杠来尝试显示每次移除后列表如何移动。

您可以通过反转删除顺序来降低复杂性（并消除我在评论中提到的错误）：

for (int i = source.Count-1; i >= 0; --i)  {
  if (Convert.ToInt32(source[i]) % 2 == 0) {
    // No need to re-check the same element during the next iteration.
    source.RemoveAt(--i);
  }
}

- Adam Liss

---

@AdamLiss 这仍然是O(n^2) :-) - Viktor Lova

@nsinreal，我认为面试官是在开玩笑，因为我们有O(n)个项目要删除，所以不可能有log(n)，它永远不可能比O(n)更好，而且在ArrayList中也不可能比O(n^2)更好。 - Saeed Amiri

@Saeed Amiri：在ArrayList中实现O(n)是可能的。Michael J. Barber有一条评论，说明如何实现。它以“跟踪”开头... - Viktor Lova

@nsinreal，Barber的回答只是对问题的错误解释。 - Saeed Amiri

@SaeedAmiri：嗯，我写这个是为了确认在ArrayList中O(n)是可能的。 - Viktor Lova