从索引存在于另一个aray中的一个数组中删除元素

Question

包含N个对象的数组A1.另一个包含表示第一个数组中索引的数字的数组A2.您需要从A2中删除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.

Answer 2

这是解决方案.

        Char[] A1 = { 'a', 'b', 'c', 'd', 'e', 'f', 'g' };
        int[] A2 = { 5, 1 };

        int k = A2.Length;

        int N = A1.Length;

        for (int i = 0; i < k; i++)
        {
            A1[A2[i]] = '\0'; // place null charcater here
        }

        Char[] copy = new char[N];

        for (int i = 0,j=0; i < N; i++) // place all values in sorted order
        {
            if (A1[i] != '\0')
                copy[j++] = A1[i];
        }
        for (int i = (N-k); i < N;i++ )
        {
            copy[i] = '-';
        }
        Console.WriteLine(copy);