三个有序数组的交集
难度:
标签:
题目描述
代码结果
运行时间: 26 ms, 内存: 16.4 MB
/*
* LeetCode Problem 1213: Intersection of Three Sorted Arrays
* Given three integer arrays arr1, arr2 and arr3 sorted in strictly increasing order,
* return a sorted array of only the integers that appeared in all three arrays.
*
* Approach using Java Streams:
* 1. Convert each array to a stream.
* 2. Convert the streams to sets to facilitate intersection operations.
* 3. Perform intersection of the sets.
* 4. Collect the result back to a list.
*/
import java.util.*;
import java.util.stream.*;
public class Solution {
public List<Integer> arraysIntersection(int[] arr1, int[] arr2, int[] arr3) {
Set<Integer> set1 = Arrays.stream(arr1).boxed().collect(Collectors.toSet());
Set<Integer> set2 = Arrays.stream(arr2).boxed().collect(Collectors.toSet());
Set<Integer> set3 = Arrays.stream(arr3).boxed().collect(Collectors.toSet());
return set1.stream()
.filter(set2::contains)
.filter(set3::contains)
.sorted()
.collect(Collectors.toList());
}
}
解释
方法:
该题解采用了三指针的方法来寻找三个有序数组的交集。每个数组都有一个指针(p1, p2, p3),开始时都指向各自数组的第一个元素。循环进行比较,如果三个指针指向的元素都相同,则该元素为交集的一部分,将其加入结果列表,并将三个指针都前移一位。如果不匹配,则移动指向最小元素的指针,以期在较大元素的数组中寻找匹配。这个过程一直进行,直到任何一个指针超出其对应数组的长度。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
为什么在三个数组元素不相等时,只移动指向最小元素的指针,而不是移动指向较大元素的指针?
▷🦆
在所有指针移动结束后,该算法如何保证不会错过任何一个可能的交集元素?
▷🦆
如果数组中存在重复元素,这种三指针方法是否还能正确地找到所有交集?
▷