5

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

问题

ArrayList编写一个程序来删除存储在contains 中的偶数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，不需要额外的花里胡哨。只是简单的循环或其他逻辑来做到这一点

4

7 回答 7

5

我敢说复杂性实际上是 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)。

于 2012-05-26T14:51:12.280 回答
4

让我们这样想：

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

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

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

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

这对你有意义吗？

于 2012-05-26T15:11:53.053 回答
2

如果您保留两个索引，一个指向当前读取位置，一个指向当前写入位置，您可以获得明显更好的性能。

int read = 0
int write = 0;

这个想法是 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)。

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

于 2012-05-26T15:20:36.427 回答
1

如果您确实必须使用 ArrayList 并且必须主动删除条目（而不是首先不添加它们）

不增加 i + 1 但 i + 2 将消除您检查它是否为奇数的需要。

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

编辑：我知道这只有source在按顺序包含 1-100 的条目时才有效。

于 2012-05-26T14:55:31.807 回答
1

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

于 2012-05-26T15:03:13.863 回答
1

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

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);
  }
}
于 2012-05-26T15:14:05.223 回答
1

如果您有无限的并行线程可用，则有可能。

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

  1. 每个线程决定它的元素是偶数还是奇数。（时间O(1)。）
  2. 确定数组中它下面有多少元素是奇数。（时间O(log(n))。）
    1. 在第二个数组中标记 0 或 1，具体取决于您在同一索引处是偶数还是奇数。所以每一个都是那个地方的赔率计数。
    2. 如果您的索引是奇数，请添加前一个数字。现在每个条目都是当前块 2 中的赔率计数，由您自己决定
    3. 如果你的索引 mod 4 是 2，在下面的索引处添加值，如果是 3，在下面添加答案 2 索引。现在，每个条目都是当前块中的赔率计数 4 由您自己决定。
    4. 继续这个模式2**i（如果你在上半部分加上下半部分的计数）次 - 现在这个数组中的每个条目都是下面的赔率计数。log2(n)
  3. 每个 CPU 将其值插入到正确的插槽中。
  4. 将数组截断为正确的大小。

I am willing to bet that something like this is the answer your friend has in mind.

于 2012-05-26T18:31:41.103 回答