赞
踩
1.给定以非递减排序的三个数组,找出这三个数组中的所有公共元素,例如,给出三个数组,arr1 = [,2,5,12,20,45,85],arr2=[16,19,20,85,200],arr3=[3,4,15,20,39,72,85,190],那么这三个数组的公共元素为[20,85]
2.解析:方法一,可以找出两个数组的交集存为临时数组,再求临时数组与第三个数组的交集。方法二:假设当前遍历的三个数组元素分别为arr1[i],arr2[j],arr3[k],则存在以下几种可能性,
(1)如果arr[i],arr2[j],arr3[k]相等,则说明当前遍历的元素是三个数组的公共元素,可以直接打印出来,然后i,j,k加一,使三个数组同时向后移动,此时继续遍历各个数组后面的元素
(2)如果arr1[i]<arr2[j],则执行i+来继续遍历arr1后面的元素
(3)如果arr2[j]<arr3[k],j+来向后遍历
(4)如果前面条件都不满足,则说明arr1[i]>arr2[j]而且arr2[j]>arr3[k],则k+继续遍历
3.代码如下:
def find_commen(arr1,arr2,arr3): i,j,k = 0,0,0 while i <len(arr1) and j < len(arr2) and k < len(arr3): if arr1[i] == arr2[j] == arr3[k]: print(arr1[i]) i += 1 j += 1 k += 1 elif arr1[i] < arr2[j]: i += 1 elif arr2[j] < arr3[k]: j += 1 else: k += 1 if __name__ == '__main__': arr1 = [2,5,12,20,45,85] arr2 = [16,19,20,85,200] arr3 = [3,4,15,20,39,72,85,190] find_commen(arr1,arr2,arr3) 结果 20 85
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。