leetcode
leetcode 1001 ~ 1050
三个有序数组的交集

三个有序数组的交集

难度:

标签:

题目描述

代码结果

运行时间: 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)

代码细节讲解

🦆
为什么在三个数组元素不相等时,只移动指向最小元素的指针,而不是移动指向较大元素的指针?
在这种算法中,目标是找到所有三个数组共同的元素。当三个指针所指的元素不相同时,意味着最小的那个元素不可能是共同元素,因为它比其他至少一个数组中的元素小。如果我们移动指向最小元素的指针,我们可以将这个指针的元素逐渐增大,试图找到一个匹配较大元素的值,从而寻找交集。反之,如果移动较大元素的指针,它们的值将会越来越大,而最小的那个元素还是不会匹配,这样做无法帮助我们找到共同元素,反而可能错过潜在的交集。
🦆
在所有指针移动结束后,该算法如何保证不会错过任何一个可能的交集元素?
算法通过仅在找到共同元素时同时移动所有三个指针来保证。如果没有找到共同元素,算法只会移动指向最小元素的那个指针,这样做是为了逐步逼近其他两个较大元素的值。通过这种方式,只要有可能形成交集的元素,这种方法最终会考虑到它们,因为其他两个指针会保持不动,直到最小的指针指向的元素增加到足够大的值去匹配它们为止。这样可以确保每个数组中的每个元素都会被考虑到,而不会遗漏任何可能的交集。
🦆
如果数组中存在重复元素,这种三指针方法是否还能正确地找到所有交集?
是的,这种三指针方法同样适用于处理包含重复元素的数组。由于数组是有序的,相同的元素会连续出现。算法在发现一组相等的元素时,会将它们加入到结果中,并同时移动所有三个指针。这意味着即使有重复元素,每个数组的指针都会在找到共同元素后移动到下一个位置,继续寻找下一个可能的交集。因此,即使数组中有重复元素,该算法也能正确地找到所有交集元素。

相关问题

两个数组的交集

给定两个数组 nums1 和 nums2 ,返回 它们的 交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序

 

示例 1:

输入:nums1 = [1,2,2,1], nums2 = [2,2]
输出:[2]

示例 2:

输入:nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出:[9,4]
解释:[4,9] 也是可通过的

 

提示:

  • 1 <= nums1.length, nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 1000