350.两个数组的交集II

LeetCode LeetCode 数组 哈希表 排序 双指针 二分查找
发布时间 :
字数:2.7k 阅读 : 评论:
  1. 350.两个数组的交集II
    1. 350.1 题目
    2. 350.2 题解
      1. 双字典
      2. 单字典
      3. 双指针法
    3. 350.3 代码
    4. 350.4 运行结果

350.两个数组的交集II

350.1 题目

给你两个整数数组 nums1 和 nums2，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。

示例 1：

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

示例 2:

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[4,9]

提示：

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

进阶：

  1. 如果给定的数组已经排好序呢？你将如何优化你的算法？
  2. 如果 nums1 的大小比 nums2 小，哪种方法更优？
  3. 如果 nums2 的元素存储在磁盘上，内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？

350.2 题解

双字典

// 方法一：双字典
// 双字典存储两数组各元素出现次数
// 遍历取最小值存到List后返回
static int[] Intersect1(int[] nums1, int[] nums2)
{
    // 创建两个字典来存储元素及其出现次数
    Dictionary<int, int> numCountMap1 = new Dictionary<int, int>();
    Dictionary<int, int> numCountMap2 = new Dictionary<int, int>();

    // 统计 nums1 中每个元素的出现次数
    foreach (int num in nums1)
    {
        if (!numCountMap1.ContainsKey(num)) // 如果 numCountMap1 中不包含当前元素
            numCountMap1[num] = 1; // 将当前元素添加到 numCountMap1，并设置其出现次数为 1
        else
            numCountMap1[num]++; // 否则，增加当前元素在 numCountMap1 中的出现次数
    }

    // 统计 nums2 中每个元素的出现次数
    foreach (int num in nums2)
    {
        if (!numCountMap2.ContainsKey(num)) // 如果 numCountMap2 中不包含当前元素
            numCountMap2[num] = 1; // 将当前元素添加到 numCountMap2，并设置其出现次数为 1
        else
            numCountMap2[num]++; // 否则，增加当前元素在 numCountMap2 中的出现次数
    }

    // 找到两个数组的交集，每个元素出现次数为较小值
    List<int> intersection = new List<int>(); // 创建一个列表来存储交集元素
    foreach (var kvp in numCountMap1) // 遍历 numCountMap1 中的每个键值对
    {
        if (numCountMap2.ContainsKey(kvp.Key)) // 如果 numCountMap2 中包含当前元素
        {
            int count = Math.Min(kvp.Value, numCountMap2[kvp.Key]); // 计算当前元素在两个数组中出现的最小次数
            for (int i = 0; i < count; i++) // 将当前元素按照最小次数添加到交集列表中
            {
                intersection.Add(kvp.Key);
            }
        }
    }

    return intersection.ToArray(); // 将交集列表转换为数组并返回
}

单字典

// 方法二：单字典
// 存储元素出现次数
// 遍历字典减少次数 添加到列表
static int[] Intersect2(int[] nums1, int[] nums2)
{
    Dictionary<int, int> numCountMap1 = new Dictionary<int, int>(); // 创建一个字典来存储 nums1 中元素及其出现次数
    List<int> intersection = new List<int>(); // 创建一个列表来存储交集元素

    // 统计 nums1 中每个元素的出现次数
    foreach (int num in nums1)
    {
        if (!numCountMap1.ContainsKey(num)) // 如果 numCountMap1 中不包含当前元素
            numCountMap1[num] = 1; // 将当前元素添加到 numCountMap1，并设置其出现次数为 1
        else
            numCountMap1[num]++; // 否则，增加当前元素在 numCountMap1 中的出现次数
    }

    // 在统计 nums2 中每个元素的同时，检查是否在 nums1 中出现过
    foreach (int num in nums2)
    {
        if (numCountMap1.ContainsKey(num) && numCountMap1[num] > 0) // 如果 num 在 numCountMap1 中存在且出现次数大于 0
        {
            intersection.Add(num); // 将当前元素添加到交集列表中
            numCountMap1[num]--; // 减少当前元素在 numCountMap1 中的出现次数
        }
    }

    return intersection.ToArray(); // 将交集列表转换为数组并返回
}

双指针法

// 方法三：双指针法
// 双数组排序后移动指针
static int[] Intersect3(int[] nums1, int[] nums2)
{
    // 对 nums1 和 nums2 进行排序，以便进行双指针遍历
    Array.Sort(nums1);
    Array.Sort(nums2);

    // 初始化两个指针的起始位置
    int index1 = 0;
    int index2 = 0;

    // 创建一个临时数组来存储交集元素
    int[] tempResultArray = new int[Math.Min(nums1.Length, nums2.Length)];

    // 用于记录实际交集数组的长度
    int realResultArrayLength = 0;

    // 双指针遍历数组，寻找交集元素
    while (index1 < nums1.Length && index2 < nums2.Length)
    {
        // 如果两个指针所指元素相等，则为交集元素
        if (nums1[index1] == nums2[index2])
        {
            // 将交集元素存入临时数组，并更新实际交集数组的长度
            tempResultArray[realResultArrayLength] = nums1[index1];
            realResultArrayLength++;

            // 更新指针位置，继续向后遍历
            index1++;
            index2++;
        }
        else
        {
            // 如果 nums1[index1] 大于 nums2[index2]，则将 index2 向后移动
            if (nums1[index1] > nums2[index2])
            {
                index2++;
            }
            // 否则，将 index1 向后移动
            else
            {
                index1++;
            }
        }
    }

    // 创建实际交集数组，长度为 realResultArrayLength
    int[] realResultArray = new int[realResultArrayLength];

    // 将临时数组中的交集元素复制到实际交集数组中
    Array.Copy(tempResultArray, realResultArray, realResultArrayLength);

    // 返回实际交集数组
    return realResultArray;
}

350.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]

        // 示例 2：
        // 输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
        // 输出：[4,9]

        // 提示：
        // 1 <= nums1.length, nums2.length <= 1000
        // 0 <= nums1[i], nums2[i] <= 1000

        #endregion

        #region 测试

        // 示例 1 方法1
        int[] nums1_1 = { 1, 2, 2, 1 };
        int[] nums2_1 = { 2, 2 };
        int[] result1_1 = Intersect1(nums1_1, nums2_1);
        Console.Write("示例1 方法1 输出：[");
        foreach (int num in result1_1)
        {
            Console.Write($"{num}, ");
        }

        Console.WriteLine("]");

        // 示例 1 方法2
        int[] nums1_2 = { 1, 2, 2, 1 };
        int[] nums2_2 = { 2, 2 };
        int[] result1_2 = Intersect2(nums1_2, nums2_2);
        Console.Write("示例1 方法2 输出：[");
        foreach (int num in result1_2)
        {
            Console.Write($"{num}, ");
        }

        Console.WriteLine("]");

        // 示例 1 方法3
        int[] nums1_3 = { 1, 2, 2, 1 };
        int[] nums2_3 = { 2, 2 };
        int[] result1_3 = Intersect3(nums1_3, nums2_3);
        Console.Write("示例1 方法3 输出：[");
        foreach (int num in result1_3)
        {
            Console.Write($"{num}, ");
        }

        Console.WriteLine("]");

        // 示例 2 方法1
        int[] nums1_4 = { 4, 9, 5 };
        int[] nums2_4 = { 9, 4, 9, 8, 4 };
        int[] result2_1 = Intersect1(nums1_4, nums2_4);
        Console.Write("示例2 方法1 输出：[");
        foreach (int num in result2_1)
        {
            Console.Write($"{num}, ");
        }

        Console.WriteLine("]");

        // 示例 2 方法2
        int[] nums1_5 = { 4, 9, 5 };
        int[] nums2_5 = { 9, 4, 9, 8, 4 };
        int[] result2_2 = Intersect2(nums1_5, nums2_5);
        Console.Write("示例2 方法2 输出：[");
        foreach (int num in result2_2)
        {
            Console.Write($"{num}, ");
        }

        Console.WriteLine("]");

        // 示例 2 方法3
        int[] nums1_6 = { 4, 9, 5 };
        int[] nums2_6 = { 9, 4, 9, 8, 4 };
        int[] result2_3 = Intersect3(nums1_6, nums2_6);
        Console.Write("示例2 方法3 输出：[");
        foreach (int num in result2_3)
        {
            Console.Write($"{num}, ");
        }

        Console.WriteLine("]");

        #endregion
    }

    #region 答案

    // 方法一：双字典
    // 双字典存储两数组各元素出现次数
    // 遍历取最小值存到List后返回
    static int[] Intersect1(int[] nums1, int[] nums2)
    {
        // 创建两个字典来存储元素及其出现次数
        Dictionary<int, int> numCountMap1 = new Dictionary<int, int>();
        Dictionary<int, int> numCountMap2 = new Dictionary<int, int>();

        // 统计 nums1 中每个元素的出现次数
        foreach (int num in nums1)
        {
            if (!numCountMap1.ContainsKey(num)) // 如果 numCountMap1 中不包含当前元素
                numCountMap1[num] = 1; // 将当前元素添加到 numCountMap1，并设置其出现次数为 1
            else
                numCountMap1[num]++; // 否则，增加当前元素在 numCountMap1 中的出现次数
        }

        // 统计 nums2 中每个元素的出现次数
        foreach (int num in nums2)
        {
            if (!numCountMap2.ContainsKey(num)) // 如果 numCountMap2 中不包含当前元素
                numCountMap2[num] = 1; // 将当前元素添加到 numCountMap2，并设置其出现次数为 1
            else
                numCountMap2[num]++; // 否则，增加当前元素在 numCountMap2 中的出现次数
        }

        // 找到两个数组的交集，每个元素出现次数为较小值
        List<int> intersection = new List<int>(); // 创建一个列表来存储交集元素
        foreach (var kvp in numCountMap1) // 遍历 numCountMap1 中的每个键值对
        {
            if (numCountMap2.ContainsKey(kvp.Key)) // 如果 numCountMap2 中包含当前元素
            {
                int count = Math.Min(kvp.Value, numCountMap2[kvp.Key]); // 计算当前元素在两个数组中出现的最小次数
                for (int i = 0; i < count; i++) // 将当前元素按照最小次数添加到交集列表中
                {
                    intersection.Add(kvp.Key);
                }
            }
        }

        return intersection.ToArray(); // 将交集列表转换为数组并返回
    }

    // 方法二：单字典
    // 存储元素出现次数
    // 遍历字典减少次数 添加到列表
    static int[] Intersect2(int[] nums1, int[] nums2)
    {
        Dictionary<int, int> numCountMap1 = new Dictionary<int, int>(); // 创建一个字典来存储 nums1 中元素及其出现次数
        List<int> intersection = new List<int>(); // 创建一个列表来存储交集元素

        // 统计 nums1 中每个元素的出现次数
        foreach (int num in nums1)
        {
            if (!numCountMap1.ContainsKey(num)) // 如果 numCountMap1 中不包含当前元素
                numCountMap1[num] = 1; // 将当前元素添加到 numCountMap1，并设置其出现次数为 1
            else
                numCountMap1[num]++; // 否则，增加当前元素在 numCountMap1 中的出现次数
        }

        // 在统计 nums2 中每个元素的同时，检查是否在 nums1 中出现过
        foreach (int num in nums2)
        {
            if (numCountMap1.ContainsKey(num) && numCountMap1[num] > 0) // 如果 num 在 numCountMap1 中存在且出现次数大于 0
            {
                intersection.Add(num); // 将当前元素添加到交集列表中
                numCountMap1[num]--; // 减少当前元素在 numCountMap1 中的出现次数
            }
        }

        return intersection.ToArray(); // 将交集列表转换为数组并返回
    }

    // 方法三：双指针法
    // 双数组排序后移动指针
    static int[] Intersect3(int[] nums1, int[] nums2)
    {
        // 对 nums1 和 nums2 进行排序，以便进行双指针遍历
        Array.Sort(nums1);
        Array.Sort(nums2);

        // 初始化两个指针的起始位置
        int index1 = 0;
        int index2 = 0;

        // 创建一个临时数组来存储交集元素
        int[] tempResultArray = new int[Math.Min(nums1.Length, nums2.Length)];

        // 用于记录实际交集数组的长度
        int realResultArrayLength = 0;

        // 双指针遍历数组，寻找交集元素
        while (index1 < nums1.Length && index2 < nums2.Length)
        {
            // 如果两个指针所指元素相等，则为交集元素
            if (nums1[index1] == nums2[index2])
            {
                // 将交集元素存入临时数组，并更新实际交集数组的长度
                tempResultArray[realResultArrayLength] = nums1[index1];
                realResultArrayLength++;

                // 更新指针位置，继续向后遍历
                index1++;
                index2++;
            }
            else
            {
                // 如果 nums1[index1] 大于 nums2[index2]，则将 index2 向后移动
                if (nums1[index1] > nums2[index2])
                {
                    index2++;
                }
                // 否则，将 index1 向后移动
                else
                {
                    index1++;
                }
            }
        }

        // 创建实际交集数组，长度为 realResultArrayLength
        int[] realResultArray = new int[realResultArrayLength];

        // 将临时数组中的交集元素复制到实际交集数组中
        Array.Copy(tempResultArray, realResultArray, realResultArrayLength);

        // 返回实际交集数组
        return realResultArray;
    }

    #endregion
}

350.4 运行结果

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

赏

©2016-2024 Tao

Built with Hexo and 3-hexo theme

×

喜欢就点赞,疼爱就打赏