c++ - 复制并取消 int 数组

Question

我有两个数组，都已排序。一个数组填充重复值，另一个数组填充应在第一个数组中取消的值。例如:

int * val = new int[11];
val[0] = 1; val[1] = 1;
val[2] = 2; val[3] = 2; val[4] = 2; val[5] = 2; 
val[6] = 3; 
val[7] = 4; 
val[8] = 5; val[9] = 5; val[10] = 5;

int * invalid = new int[2]; invalid[0] = 2; invalid[1] = 5;

那么输出应该是这样的

int * valid = new int[4];
valid[0] = 1; valid[1] = 1;
valid[2] = 3; 
valid[3] = 4;

如何使用 for 循环有效地实现它？我想指出，我不想切换到像 vector 或 list 这样的容器，因为我知道会有评论朝那个方向发展。我明确想要使用数组。

Answer 1

如果两者都已排序，这只是一个简单的 O(N+M) 算法:从索引为零的两个数组开始，递增指向较小值的数组。如果您增加了目标数组，则复制，除非它等于无效数组。

另外，因为你只是删除项目，如果你不必保留原始数据，你可以避免一些拷贝:你可以保留一个计数器你丢弃了多少项目，并复制到同一个数组中 currentIdx-discardedCount 如果 discardedCount 大于零。