时间戳

首页 > 解决方案 > 查找序列中的剩余元素

c# - 查找序列中的剩余元素

问题描述

每个人。我有这个小任务要做：

有两个数字序列：

  1. A[0]、A[1]、...、A[n]。

  2. B[0]、B[1]、...、B[m]。

对序列 A 进行以下操作：

  1. 删除索引可被 B[0] 整除的项目。

  2. 在剩下的项目中，删除那些索引可以被 B[1] 整除的项目。

  3. 重复这个过程直到 B[m]。

  4. 输出项目终于剩下了。

输入是这样的：（其中 -1 是两个序列 A 和 B 的分隔符）

1 2 4 3 6 5 -1 2 -1

这是我的代码（通过评论完成解释）：

List<int> result = new List<int>(); // list for sequence A
List<int> values = new List<int>(); // list for holding value to remove

var input = Console.ReadLine().Split().Select(int.Parse).ToArray();
var len = Array.IndexOf(input, -1); // getting index of the first -1 (delimiter)
result = input.ToList(); // converting input array to List
result.RemoveRange(len, input.Length - len); // and deleting everything beyond first delimiter (including it) 

for (var i = len + 1; i < input.Length - 1; i++) // for the number of elements in the sequence B
{
    for (var j = 0; j < result.Count; j++) // going through all elmnts in sequence A
    {
        if (j % input[i] == 0) // if index is divisible by B[i]
        {
            values.Add(result[j]); // adding associated value to List<int> values
        }
    }
    foreach (var value in values) // after all elements in sequence A have been looked upon, now deleting those who apply to criteria
    {
        result.Remove(value);
    }
}

但问题是我只通过了 5/11 测试用例。25% 是“错误结果”，其余 25% - “超时”。我知道我的代码可能写得很糟糕，但我真的无法理解如何改进它。

所以，如果有经验的人可以向我解释（澄清）下一点，那就太酷了：

1 . 我是否正在从控制台输入进行解析？我觉得它可以以更优雅/更有效的方式完成。

2 . 我获取适用于标准的价值然后将它们存储以供以后删除的逻辑在性能方面是否有效？或者有没有其他方法可以做到这一点？

3 . 为什么这段代码没有通过所有测试用例，或者你将如何更改它以通过所有测试用例？

标签： c#algorithmperformanceconsole

解决方案

我再次写下答案，因为我完全误解了这个问题。因此，毫无疑问，您的代码中的问题是删除了元素。让我们尽量避免这种情况。让我们尝试创建一个新数组 C，您可以在其中存储每次删除后应该留在 A 数组中的所有正确数字。因此，如果索引 id 不能被 B[i] 整除，则应将 A[id] 添加到数组 C。然后，在使用 B[i] 值检查所有索引后，应将数组 A 替换为数组 C并对 B[i + 1] 做同样的事情。重复直到到达数组 B 的末尾。

算法：

 1. For each value in B:
       2. For each id from 1 to length(A):
                3. If id % value != 0, add A[id] to C             
       4. A = C
 5. Return A.

编辑：确保为 1. 循环的每次迭代创建一个新数组 C（或在用它替换 A 后清除 C）

推荐阅读