问答题 2.  给定以非递减顺序排序的三个数组,找出这三个数组中的所有公共元素。例如,给出下面三个数组: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]不可能是三个数组公共的元素。
   (3)如果ar2[j]<ar3[k],同理可以通过j+来继续遍历ar2后面的元素。
   (4)如果前面的条件都不满足,说明ar1[i]>ar2[j]而且ar2[j]>ar3[k],此时可以通过k+来继续遍历ar3后面的元素。
   实现代码如下:
   def findCommon(ar1,ar2,ar3):
   i=0
   j=0
   k=0
   n1=len(ar1)
   n2=len(ar2)
   n3=len(ar3)
   #遍历三个数组
   while i<n1 and j<n2 and k<n3:
   #找到了公共元素
   if ar1[i]==ar2[j] and ar2[j]==ar3[k]:
   print ar1[i],
   i+=1
   j+=1
   k+=1
   #ar[i]不可能是公共元素
   elif ar1[i]<ar2[j]:
   i+=1
   #ar2[j]不可能是公共元素
   elif ar2[j]<ar3[k]:
   j+=1
   #ar3[k]不可能是公共元素
   else:
   k+=1
   
   if __name__=="__main__":
   ar1=[2,5,12,20,45,85]
   ar2=[16,19,20,85,200]
   ar3=[3,4,15,20,39,72,85,190]
   fidCommon(ar1, ar2, ar3)
   程序的运行结果为:
   20 85
   算法性能分析:
   这种方法的时间复杂度为O(N1+N2+N3)。
【答案解析】[考点] 如何从三个有序数组中找出它们的公共元素