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 <= 10000 <= nums1[i], nums2[i] <= 1000
349.2 题解
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();
}
排序双指针
// 方法二：排序双指针
// 对两个数组排序，双指针分别遍历两个数组，元素相等加到交集列表移动两个指针，不等移动较小的指针，返回交集列表变成数组
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
