Question

今天我被问到这个我知道答案非常简单但是他让我保持了最后的转折

Question

写入一个程序, 以删除存储在 ArrayList 中的包含 1 - 100 的偶数。

I just said wow

在这里,你走了这是我是如何实施它。

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

The twist

他问我这个过程的计算复杂程度给了他一个方程式。我刚刚做了,说这是线性直接与N(投入)成正比。

他说: hmm. 。这意味着当输入尺寸增加的时候, 我需要等待更长的时间才能得到结果? 是 sirr you are

为我发号施令,让它做 Log(N) 尽可能多地尝试他所说的话。

Hence come here for the right logic, answer or algorithm to do this.

\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \

Answer 1

让我们这样想:

您正在做的删除动作的数量是, 强制的, lenght 数组的一半( 如果元素存储在数组中) 。所以复杂性至少是 O( N) 。

你收到的问题让我猜想你的教授想让你解释如何用不同的方式储存数字

通常情况下,当您的日志复杂时,您要使用不同的结构,如图表或树。

我唯一能想到的对数复杂性的方法就是把数字储存在树上(有顺序的树,b-tree...我们用圆柱子来阐述这一点), 但实际上这是你考试的限制(数组数组数组数组数组数组) 。

你觉得合理吗?

Answer 2

我敢说,复杂性实际上是O(N)2,因为阵列中的清除是O(N),而且每个项目都有可能需要。

所以,对于每次移除的数组(列表)和O(N),您都有O(N),O(N)为 gt;O(N) * O(N)。

由于似乎不清楚,我将解释推理。每一步都可能删除一个项目(假设每个项目都必须删除的最坏情况)。在一个阵列中,删除是通过移动进行的。因此,要删除第一个项目,我需要将以下所有N-1项目移到左边一个位置:

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

现在,在每次迭代时,我都需要转换, 所以我正在做 < code> N-1 + N-2 +... + 1 + 0 轮移, 由此产生了 < code> (N) * (N-1) / 2 (Aariphet 序列) 的结果, 使 O(N) 2 具有最后的复杂性。

Answer 3

如果您保留两个索引, 一个到当前读取位置, 一个到当前写入位置, 您可以得到明显更好的业绩。

int read = 0
int write = 0;

想法是,读取时会依次查看数组的每个成员; 写时会跟踪列表的当前结尾。当我们找到想要删除的成员时, 我们向前移动读取, 而不是写取。

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

然后在结尾告诉阵列列表,它的新长度是“ write”的当前值。

这把您从原来的 O(n) 2 到 O(n) 。

(注:我还没有测试过这个)

Answer 4

在不改变数据结构或不对项目在矩阵列表中存储的方式做出某种假设的情况下,我看不出你如何避免检查每个成员之间的对等性(至少是 O(n) 复杂程度 ) 。也许采访者只是希望你告诉他这是不可能的。

Answer 5

如果您真的需要使用矩阵列表, 并且要积极删除条目( 而不是首先添加它们) 。

不因 i + 1 而因 i + 2 递增将消除您检查是否奇特的需要。

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

<% 1 > 编辑 < / strong > : 我知道这只有在 < code> 源代码按顺序包含 1- 100 条目时才有效。

Answer 6

给定的解决方案问题在于它从头开始, 所以每删除一个项目, 整个列表都必须被移动 :

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);
  }
}

Answer 7

您可能拥有无限的平行线条。

假设我们有一个包含 n 元素的阵列。每个元素指派一个线条。假设所有线条都同步运行。

Each thread decides whether its element is even or odd. (Time O(1).)
Determine how many elements below it in the array are odd. (Time O(log(n)).)
1. Mark a 0 or 1 in an second array depending whether you are even or odd at the same index. So each one is a count of odds at that spot.
2. If your index is odd, add the previous number. Now each entry is a count of odds in the current block of 2 up to yourself
3. If your index mod 4 is 2, add the value at the index below, if it is 3, add the answer 2 indexes below. Now each entry is a count of odds in the current block of 4 up to yourself.
4. Continue this pattern with blocks of 2**i (if you re in the top half add the count for the bottom half) log₂(n) times - now each entry in this array is the count of odds below.
Each CPU inserts its value into the correct slot.
Truncate the array to the right size.

我敢打赌,这样的事是你的朋友想得到的答案

Question

I just said wow

The twist

友情链接