难度: Easy
Submission
运行时间: 26 ms
内存: 16.4 MB
class Solution:
def arraysIntersection(self, arr1: List[int], arr2: List[int], arr3: List[int]) -> List[int]:
res = []
p1 = 0
p2 = 0
p3 = 0
n1 = len(arr1)
n2 = len(arr2)
n3 = len(arr3)
while p1 < n1 and p2 < n2 and p3 < n3:
if arr1[p1] == arr2[p2] and arr2[p2] == arr3[p3]:
res.append(arr1[p1])
p1 += 1
p2 += 1
p3 += 1
else:
if arr1[p1] < arr2[p2]:
p1 += 1
elif arr2[p2] < arr3[p3]:
p2 += 1
else:
p3 += 1
return res
Explain
该题解采用了三指针的方法来寻找三个有序数组的交集。每个数组都有一个指针（p1, p2, p3），开始时都指向各自数组的第一个元素。循环进行比较，如果三个指针指向的元素都相同，则该元素为交集的一部分，将其加入结果列表，并将三个指针都前移一位。如果不匹配，则移动指向最小元素的指针，以期在较大元素的数组中寻找匹配。这个过程一直进行，直到任何一个指针超出其对应数组的长度。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def arraysIntersection(self, arr1: List[int], arr2: List[int], arr3: List[int]) -> List[int]:
# 结果列表
res = []
# 初始化三个数组的指针
p1, p2, p3 = 0, 0, 0
# 获取三个数组的长度
n1, n2, n3 = len(arr1), len(arr2), len(arr3)
# 当三个指针都没有越界时循环
while p1 < n1 and p2 < n2 and p3 < n3:
# 如果三个指针指向的元素相等
if arr1[p1] == arr2[p2] and arr2[p2] == arr3[p3]:
res.append(arr1[p1]) # 加入到结果列表
p1 += 1 # 三个指针同时前进
p2 += 1
p3 += 1
else:
# 移动指向最小元素的指针
if arr1[p1] < arr2[p2]:
p1 += 1
elif arr2[p2] < arr3[p3]:
p2 += 1
else:
p3 += 1
return res # 返回结果列表
Explore
在这种算法中，目标是找到所有三个数组共同的元素。当三个指针所指的元素不相同时，意味着最小的那个元素不可能是共同元素，因为它比其他至少一个数组中的元素小。如果我们移动指向最小元素的指针，我们可以将这个指针的元素逐渐增大，试图找到一个匹配较大元素的值，从而寻找交集。反之，如果移动较大元素的指针，它们的值将会越来越大，而最小的那个元素还是不会匹配，这样做无法帮助我们找到共同元素，反而可能错过潜在的交集。
算法通过仅在找到共同元素时同时移动所有三个指针来保证。如果没有找到共同元素，算法只会移动指向最小元素的那个指针，这样做是为了逐步逼近其他两个较大元素的值。通过这种方式，只要有可能形成交集的元素，这种方法最终会考虑到它们，因为其他两个指针会保持不动，直到最小的指针指向的元素增加到足够大的值去匹配它们为止。这样可以确保每个数组中的每个元素都会被考虑到，而不会遗漏任何可能的交集。
是的，这种三指针方法同样适用于处理包含重复元素的数组。由于数组是有序的，相同的元素会连续出现。算法在发现一组相等的元素时，会将它们加入到结果中，并同时移动所有三个指针。这意味着即使有重复元素，每个数组的指针都会在找到共同元素后移动到下一个位置，继续寻找下一个可能的交集。因此，即使数组中有重复元素，该算法也能正确地找到所有交集元素。