查找两个排序数组的相对补集

在本节课中，我们将学习如何查找两个已排序数组的相对补集。

已排序数组是指按照指定顺序（字母顺序、时间顺序、序数顺序、基数顺序）组织的数组。未排序数组是指没有任何顺序的数组。

假设有两个已排序数组：array1 和 array2，其大小分别为 p 和 q。我们需要确定两个数组的相对补集，array1 - array2，这意味着我们需要找到 array1 中所有存在但不存在于 array2 中的元素。

示例

• 考虑两个指针 i 和 j，它们分别遍历 array1 和 array2。
• 如果 array1[i] 元素小于 array2[j] 元素，则打印它并递增 i。
• 如果 array1[i] 高于 array2[j] 元素，则递增 j。
• 否则，同时递增 i 和 j。

实施

C++ 程序

输出

6 12 15

• 时间复杂度为 O(p + q)。
• 辅助空间为 O(1)。