java - 需要优化算法 - 数组

Question

我们有一个大小为 N 的整数数组 A。给定另一个包含索引的数组 B，其中 size of B <= N和 0<=B[i]<=N-1 .

现在我们必须删除数组 A 中位置 B[i] 的所有元素.

所以对于删除，我们的意思是我们也在移动数组 A 中的元素。

谁能帮我联系到O(n)这个问题的解决方案？可能还有 O(1) 空间。

我想到的第一个方案是，遍历数组B，依次删除A中的元素(包括移位)，结果是O(n^2) .

Answer 1

类似于 iliaden 的解决方案，不同之处在于您可以就地删除已删除的元素。

int[] a = 
int[] b = 
int nullValue = 
for(int i: b) a[i] = nullValue;
int j=0;
for(int i=0; i < a.length; i++) {
    if(a[i] != nullValue)
       a[j++] = a[i];
}
// to clear the rest of the array, if required.
for(;j<a.length;j++)
   a[j] = nullValue;

注意:a 不会更短，但可以避免创建更多空间。 'j' 将包含 a

中的有效条目数