如何从三个有序数组中找出它们的公共元素？

Nen 2022-03-28 13:47

- 程序员

最容易想到的方法是首先找出两个数组的交集，然后再把这个交集存储在一个临时数组中，最后再找出这个临时数组与第三个数组的交集。这种方法的时间复杂度为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后面的元素。

如何从三个有序数组中找出它们的公共元素？

轩辕小不懂的其他提问

类似问题

如何从三个有序数组中找出它们的公共元素？

轩辕小不懂 的其他提问

类似问题

轩辕小不懂的其他提问