arrays - 删除和移动数组元素

Question

假设我有 2 个排序数组。其中一个具有要从另一个删除的元素。 例如

  int array1[]={1,2,3,4,5,6,7,8,9,10,11,12,13};
  int delete[]={5,9,12};

如何高效地从array1中删除delete数组中指示的元素，并将剩余的元素移动到array1中？

我不想遍历 array1 的所有元素，因为其中一些元素将保持不变。所以我想从

  int j,i=0,n=0;
  for(j=delete[i+n];j<delete[i+1+n];j++){
      array1[i-n]=array1[i+1-n];
      n++;
  }

但我不太清楚如何正确地做到这一点。有什么想法吗？

Answer 1

从数组中删除任何元素是一个 O(N) 操作。您可以执行以下操作。

1. 初始化 i = 0。count = 0。
2. 遍历 array1[] 并搜索元素 delete[i]。
3. 如果遇到元素array1[j] > delete[i]，说明delete[i]在array[]中不存在。递增 i 以检查删除数组中的下一个元素。
4. 如果找到元素 array1[j] == delete[i]，则递增计数。并增加我。

5. 继续将 array1[j] 复制到 array1[j - count]。

   array1[j - count] = array1[j];

6. 继续到 array1 的末尾。最后，将 array1 的大小调整为 size - count。