arrays - 在两个排序数组中查找缺失的数字

Question

我遇到一道面试题。

给定两个排序数组。
最初两者都有一组元素，但一个元素从一个数组中删除。
找到删除的元素。
约束是我们必须在 O(logn) 中就地完成它 例如:

arr1[]={1,2,3,8,12,16};
arr2[]={1,2,8,12,16};

删除的元素是3

Answer 1

我是用手机输入的，所以它是一个伪代码，但你会明白的:

取arr1.len/2。它是3。检查arr1[3]和arr2[3]。如果它们相等，则缺失的 vsalue 在索引中大于 3，否则小于 3。这里我们得到 8 和 12。所以缺失是之前。我们取索引 3/2=1。比较 arr1[1] 和 arr2[1]。它们是相等的，所以 missing 是在索引 1 之后和 3 之前。所以它是 arr1[2] = 3。

这就是想法。您正在进行二进制搜索，每次将搜索区域减半。根据比较，您可以获取数组的左侧或右侧部分。您只需要实现它并进行一些检查，但我认为这个想法很明确。