c# - 从一个数组中删除其索引存在于另一个数组中的元素

Question

一个数组 A1 包含 N 个对象。另一个数组 A2 包含代表第一个数组索引的数字。您需要从 A1 中删除 A2 中存在索引的元素并生成压缩数组。例如:

A1 = [ a, b, c, d, e, f, g ] // N elements and N is large
A2 = [ 5, 1 ] // k elements and k is small (and constant)
Answer = [ a, c, d, e, g, _, _ ]

我写的 C# 代码如下:

public class CompactingArray
{
    private Compact(array A1 , array A2)
    {
        var hash = new Hashset<int>(A2);
        foreach(int c in hash)
        {
            A1.remove(c,1);
        }

        Console.WriteLine(A1);
    }
}

我需要复杂度为 O(n) 的代码并且不使用任何内置函数。请建议不使用任何内置函数的 C# 代码。

Answer 1

如果 k，即 A2 中的元素数，是“小而恒定”的，那么复杂度为 O(N*k) 的简单算法(对于每个元素在 A1 中查看其索引是否在 A2 中)将被视为线性:

int writingPosition = 0;
for (int i = 0 ; i != N ; i++) {
    boolean found = false;
    // Since k is constant, this loop is considered constant-time
    for (int j = 0 ; j != k ; j++) {
        if (A2[j] == i) {
            found = true;
            break;
        }
    }
    if (!found) {
        A1[writingPosition++] = A1[i];
    }
}
while (writingPosition != N) {
    A1[writingPosition++] = "_";
}

但是，这并不是最佳选择。为了提高性能，您可以对 A2 进行排序(对它进行排序是一个常量时间操作)。一旦 A2 被排序，你可以创建一个 int current=0，一个 A2 的索引，然后遍历 A1 从零到 N 的数组，并跳过 A2[current] 的索引。在循环到 N 的每次迭代中，您只需查看“A2”的一个元素，因此整体算法也是线性的。

实现与上面类似，但不是使用嵌套循环和检查 if (!found)，而是检查 A2[current] == i，并相应地调整 current。