这是我作为编程练习使用的面试问题.
输入:分别按递增顺序和不同大小N和M的两个排序整数数组A和B.
输出:按升序排序的排序整数数组C,包含出现在A和B中的元素
对比: C中不允许重复
示例:对于输入A = {3,6,8,9}且B = {4,5,6,9,10,11},输出应为C = {6,9}
谢谢你的回答,全部!总而言之,这个问题有两种主要方法:
我最初的解决方案是保留两个指针,每个指针对应一个数组,并从左到右交替扫描数组,同时选择匹配的元素.因此,当我们一个数组的当前元素大于第二个数组时,我们继续递增第二个数组的指针,直到我们找到当前的第一个数组元素或者超过它(找到一个更大的数组).我保持所有匹配在一个单独的数组中,一旦我们到达任何一个输入数组的末尾就返回.
我们可以做到这一点的另一种方法是线性扫描其中一个数组,同时使用二进制搜索在第二个数组中查找匹配.这将意味着O(N*log(M))时间,如果我们扫描A并且对于其N个元素中的每一个在B上进行二进制搜索(O(log(M))时间).
我已经实现了两种方法,并进行了一项实验,看看这两种方法的比较(详情请参见此处).当N具有100万个元素时,当M大约是N的70倍时,二元搜索方法似乎获胜.