【出自YMX笔试题】
难度系数：★★★★☆ 被考察系数：★★★☆☆
题目描述：
给定以非递减顺序排序的三个数组，找出这三个数组中的所有公共元素。例如，给出下面三个数组：ar1[]={2，5，12，20，45，85}，ar2[]={16，19，20，85，200}，ar3[]={3，4，15，20，39，72，85，190}。那么这三个数组的公共元素为{20，85}。
分析与解答：
最容易想到的方法是首先找出两个数组的交集，然后再把这个交集存储在一个临时数组中，最后再找出这个临时数组与第三个数组的交集。这种方法的时间复杂度为O（N1+N2+N3），其中N1、N2和N3分别为三个数组的大小。这种方法不仅需要额外的存储空间，而且还需要额外的两次循环遍历。下面介绍另外一种只需要一次循环遍历、而且不需要额外存储空间的方法，主要思路如下：
假设当前遍历的三个数组的元素分别为ar1[i]、ar2[j]和ar3[k]，则存在以下几种可能性：
（1）如果ar1[i]、ar2[j]和ar3[k]相等，则说明当前遍历的元素是三个数组的公有元素，可以直接打印出来，然后通过执行i++，j++，k++，使三个数组同时向后移动，此时继续遍历各数组后面的元素。
（2）如果ar1[i]＜ar2[j]，则执行i++来继续遍历ar1中后面的元素，因为ar1[i]不可能是三个数组公有的元素。(www.xing528.com)
（3）如果ar2[j]＜ar3[k]，同理可以通过j++来继续遍历ar2后面的元素。
（4）如果前面的条件都不满足，说明ar1[i]＞ar2[j]而且ar2[j]＞ar3[k]，此时可以通过k++来继续遍历ar3后面的元素。
实现代码如下：
程序的运行结果如下：
20 85
算法性能分析：
这种方法的时间复杂度为O（N1+N2+N3）。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
