349.两个数组的交集

LeetCode LeetCode 数组 哈希表 双指针 排序 二分查找
发布时间 :
字数:2k 阅读 : 评论:
  1. 349.两个数组的交集
    1. 349.1 题目
    2. 349.2 题解
      1. 方法一：List存储交集元素
        1. 思路
        2. 复杂度分析
        3. 代码
      2. 方法二：排序双指针
        1. 思路
        2. 复杂度分析
        3. 代码
    3. 349.3 代码
    4. 349.4 运行结果

349.两个数组的交集

349.1 题目

给定两个数组 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

349.2 题解

方法一：List存储交集元素

思路

先将 nums1 去重存入 List，然后遍历 nums2，如果元素在 List 中且未加入交集，则加入交集 List。最后返回交集数组。

具体步骤：

  1. 遍历 nums1，将不重复的元素存入 nums1List。
  2. 遍历 nums2，如果元素在 nums1List 中且不在 intersectList 中，则加入 intersectList。
  3. 返回 intersectList 转换后的数组。

举例：对于 nums1 = [1,2,2,1], nums2 = [2,2]：

  • nums1List：[1, 2]（去重）
  • 遍历 nums2：2 在 nums1List 中，加入交集；2 已在交集中，跳过
  • 结果：[2]

复杂度分析

  • 时间复杂度：O(n × m)，Contains 操作是线性查找。
  • 空间复杂度：O(n + m)，存储两个 List。

代码

// 方法一：List存储交集元素
// 使用List找交集
static int[] Intersect1(int[] nums1, int[] nums2)
{
    // 创建一个 List 用于存储不重复的 nums1 元素
    List<int> nums1List = new List<int>();

    // 遍历 nums1 数组
    for (int i = 0; i < nums1.Length; i++)
    {
        // 判断 nums1List 中是否已包含当前元素
        if (!nums1List.Contains(nums1[i]))
        {
            // 如果不包含，将当前元素添加到 nums1List 中
            nums1List.Add(nums1[i]);
        }
    }

    // 使用 List 存储交集元素
    List<int> intersectList = new List<int>();

    // 遍历 nums2 数组
    for (int i = 0; i < nums2.Length; i++)
    {
        // 判断当前元素是否存在于 nums1List 中且还未被加入交集
        if (nums1List.Contains(nums2[i]) && !intersectList.Contains(nums2[i]))
        {
            // 将当前元素加入交集 List
            intersectList.Add(nums2[i]);
        }
    }

    // 将 List 转换为数组并返回
    return intersectList.ToArray();
}

方法二：排序双指针

思路

先对两个数组排序，然后使用双指针遍历。如果两指针指向的元素相等，加入交集并同时移动；如果不等，移动较小元素的指针。

核心思想：排序后利用单调性，双指针快速找到交集。

具体步骤：

  1. 对 nums1 和 nums2 排序。
  2. 初始化双指针 nums1Index = 0，nums2Index = 0。
  3. 遍历两个数组：
    • 如果 nums1[nums1Index] == nums2[nums2Index]：加入交集（去重），两指针都前进
    • 如果 nums1[nums1Index] < nums2[nums2Index]：nums1Index++
    • 如果 nums1[nums1Index] > nums2[nums2Index]：nums2Index++
  4. 返回交集数组。

举例：对于 nums1 = [4,9,5], nums2 = [9,4,9,8,4]：

  • 排序后：nums1 = [4,5,9]，nums2 = [4,4,8,9,9]
  • i=0, j=0：4 == 4，加入交集 [4]，i=1, j=1
  • i=1, j=1：5 > 4，j=2
  • i=1, j=2：5 < 8，i=2
  • i=2, j=2：9 > 8，j=3
  • i=2, j=3：9 == 9，加入交集 [4,9]，i=3, j=4
  • i=3 越界，结束
  • 结果：[4,9]

复杂度分析

  • 时间复杂度：O(n log n + m log m)，排序时间。
  • 空间复杂度：O(1) 或 O(n)，取决于排序算法。

代码

// 方法二：排序双指针
// 对两个数组排序，双指针分别遍历两个数组，元素相等加到交集列表移动两个指针，不等移动较小的指针，返回交集列表变成数组
static int[] Intersect2(int[] nums1, int[] nums2)
{
    // 对数组 nums1 进行排序
    Array.Sort(nums1);

    // 对数组 nums2 进行排序
    Array.Sort(nums2);

    // 用于存储交集元素的 List
    List<int> intersectList = new List<int>();

    // 初始化两个数组的索引
    int nums1Index = 0;
    int nums2Index = 0;

    // 使用双指针遍历两个排序后的数组
    while (nums1Index < nums1.Length && nums2Index < nums2.Length)
    {
        // 如果两个元素相等，表示找到一个交集元素
        if (nums1[nums1Index] == nums2[nums2Index])
        {
            // 判断交集中是否已包含当前元素，避免重复添加相同的元素
            if (!intersectList.Contains(nums1[nums1Index]))
            {
                // 将当前元素加入交集 List
                intersectList.Add(nums1[nums1Index]);
            }

            // 向前移动两个数组的索引
            nums1Index++;
            nums2Index++;
        }
        // 如果 nums1 数组中的元素小于 nums2 数组中的元素
        else if (nums1[nums1Index] < nums2[nums2Index])
        {
            // 只需将 nums1 的索引向前移动，因为较小的元素可能在 nums1 数组中找到匹配
            nums1Index++;
        }
        // 如果 nums1 数组中的元素大于 nums2 数组中的元素
        else if (nums1[nums1Index] > nums2[nums2Index])
        {
            // 只需将 nums2 的索引向前移动，因为较小的元素可能在 nums2 数组中找到匹配
            nums2Index++;
        }
    }

    // 将 List 转换为数组并返回
    return intersectList.ToArray();
}

349.3 代码

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        #region 题目

        // 给定两个数组 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

        #endregion

        #region 测试

        // 示例 1
        int[] nums1 = { 1, 2, 2, 1 };
        int[] nums2 = { 2, 2 };
        int[] result1 = Intersect1(nums1, nums2);
        Console.WriteLine($"示例1 方法1 输出：[{string.Join(", ", result1)}]");
        int[] result1_2 = Intersect2(nums1, nums2);
        Console.WriteLine($"示例1 方法2 输出：[{string.Join(", ", result1_2)}]");

        // 示例 2
        int[] nums3 = { 4, 9, 5 };
        int[] nums4 = { 9, 4, 9, 8, 4 };
        int[] result2 = Intersect1(nums3, nums4);
        Console.WriteLine($"示例2 方法1 输出：[{string.Join(", ", result2)}]");
        int[] result2_2 = Intersect2(nums3, nums4);
        Console.WriteLine($"示例2 方法2 输出：[{string.Join(", ", result2_2)}]");

        #endregion
    }

    #region 答案

    // 方法一：List存储交集元素
    // 使用List找交集
    static int[] Intersect1(int[] nums1, int[] nums2)
    {
        // 创建一个 List 用于存储不重复的 nums1 元素
        List<int> nums1List = new List<int>();

        // 遍历 nums1 数组
        for (int i = 0; i < nums1.Length; i++)
        {
            // 判断 nums1List 中是否已包含当前元素
            if (!nums1List.Contains(nums1[i]))
            {
                // 如果不包含，将当前元素添加到 nums1List 中
                nums1List.Add(nums1[i]);
            }
        }

        // 使用 List 存储交集元素
        List<int> intersectList = new List<int>();

        // 遍历 nums2 数组
        for (int i = 0; i < nums2.Length; i++)
        {
            // 判断当前元素是否存在于 nums1List 中且还未被加入交集
            if (nums1List.Contains(nums2[i]) && !intersectList.Contains(nums2[i]))
            {
                // 将当前元素加入交集 List
                intersectList.Add(nums2[i]);
            }
        }

        // 将 List 转换为数组并返回
        return intersectList.ToArray();
    }


    // 方法二：排序双指针
    // 对两个数组排序，双指针分别遍历两个数组，元素相等加到交集列表移动两个指针，不等移动较小的指针，返回交集列表变成数组
    static int[] Intersect2(int[] nums1, int[] nums2)
    {
        // 对数组 nums1 进行排序
        Array.Sort(nums1);

        // 对数组 nums2 进行排序
        Array.Sort(nums2);

        // 用于存储交集元素的 List
        List<int> intersectList = new List<int>();

        // 初始化两个数组的索引
        int nums1Index = 0;
        int nums2Index = 0;

        // 使用双指针遍历两个排序后的数组
        while (nums1Index < nums1.Length && nums2Index < nums2.Length)
        {
            // 如果两个元素相等，表示找到一个交集元素
            if (nums1[nums1Index] == nums2[nums2Index])
            {
                // 判断交集中是否已包含当前元素，避免重复添加相同的元素
                if (!intersectList.Contains(nums1[nums1Index]))
                {
                    // 将当前元素加入交集 List
                    intersectList.Add(nums1[nums1Index]);
                }

                // 向前移动两个数组的索引
                nums1Index++;
                nums2Index++;
            }
            // 如果 nums1 数组中的元素小于 nums2 数组中的元素
            else if (nums1[nums1Index] < nums2[nums2Index])
            {
                // 只需将 nums1 的索引向前移动，因为较小的元素可能在 nums1 数组中找到匹配
                nums1Index++;
            }
            // 如果 nums1 数组中的元素大于 nums2 数组中的元素
            else if (nums1[nums1Index] > nums2[nums2Index])
            {
                // 只需将 nums2 的索引向前移动，因为较小的元素可能在 nums2 数组中找到匹配
                nums2Index++;
            }
        }

        // 将 List 转换为数组并返回
        return intersectList.ToArray();
    }

    #endregion
}

349.4 运行结果

示例1 方法1 输出：[2]
示例1 方法2 输出：[2]
示例2 方法1 输出：[9, 4]
示例2 方法2 输出：[4, 9]
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com

赏

©2016-2026 Tao

Built with Hexo and 3-hexo theme

×

喜欢就点赞,疼爱就打赏