【算法千题案例】⚡️每日LeetCode打卡⚡️——52.两个数组的交集
【算法千题案例】⚡️每日LeetCode打卡⚡️——52.两个数组的交集
呆呆敲代码的小Y
发布于 2021-10-15 15:07:56
发布于 2021-10-15 15:07:56
文章被收录于专栏：呆呆敲代码的小Y 公众号
请添加图片描述
给定两个数组，编写一个函数来计算它们的交集。
示例:
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]示例 2：
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]输出结果中的每个元素一定是唯一的。
我们可以不考虑输出结果的顺序。????C#方法：排序
- 计算两个数组的交集，直观的方法是遍历数组 nums1，对于其中的每个元素，遍历数组 nums2 判断该元素是否在数组 nums2 中，如果存在，则将该元素添加到返回值。
- 假设数组 nums1 和 nums2 的长度分别是 m和 n，则遍历数组 nums1 需要 O(m) 的时间，判断 nums1 中的每个元素是否在数组 nums2 中需要 O(n) 的时间，因此总时间复杂度是O(mn)。
- 如果使用哈希集合存储元素，则可以在O(1) 的时间内判断一个元素是否在集合中，从而降低时间复杂度。
- 首先使用两个集合分别存储两个数组中的元素，然后遍历较小的集合，判断其中的每个元素是否在另一个集合中，如果元素也在另一个集合中，则将该元素添加到返回值。
- 该方法的时间复杂度可以降低到 O(m+n)
代码：
public class Solution {
public int[] Intersection(int[] nums1, int[] nums2) {
HashSet<int> set1 = new HashSet<int>();
HashSet<int> set2 = new HashSet<int>();
foreach(int num in nums1)
{
set1.Add(num);
}
foreach(int num in nums2)
{
set2.Add(num);
}
return GetIntersection(set1,set2);
}
public int[] GetIntersection(HashSet<int> set1,HashSet<int> set2)
{
if(set1.Count()>set2.Count())
{
return GetIntersection(set2,set1);
}
HashSet<int> intersection = new HashSet<int>();
foreach(int num in set1)
{
if(set2.Contains(num))
{
intersection.Add(num);
}
}
int[] answer = new int[intersection.Count()];
int i = 0;
foreach(var num in intersection)
{
answer[i] = num;
i++;
}
return answer;
}
}执行结果
通过
执行用时：132 ms，在所有 C# 提交中击败了97.37%用户
内存消耗：40.6 MB，在所有 C# 提交中击败了5.26%的用户Java 方法：两个集合
思路解析
- 计算两个数组的交集，直观的方法是遍历数组 nums1，对于其中的每个元素，遍历数组 nums2 判断该元素是否在数组 nums2 中，如果存在，则将该元素添加到返回值。
- 假设数组 nums1 和 nums2 的长度分别是 m和 n，则遍历数组 nums1 需要 O(m) 的时间，判断 nums1 中的每个元素是否在数组 nums2 中需要 O(n) 的时间，因此总时间复杂度是O(mn)。
- 如果使用哈希集合存储元素，则可以在O(1) 的时间内判断一个元素是否在集合中，从而降低时间复杂度。
- 首先使用两个集合分别存储两个数组中的元素，然后遍历较小的集合，判断其中的每个元素是否在另一个集合中，如果元素也在另一个集合中，则将该元素添加到返回值。
- 该方法的时间复杂度可以降低到 O(m+n)
代码：
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> set1 = new HashSet<Integer>();
Set<Integer> set2 = new HashSet<Integer>();
for (int num : nums1) {
set1.add(num);
}
for (int num : nums2) {
set2.add(num);
}
return getIntersection(set1, set2);
}
public int[] getIntersection(Set<Integer> set1, Set<Integer> set2) {
if (set1.size() > set2.size()) {
return getIntersection(set2, set1);
}
Set<Integer> intersectionSet = new HashSet<Integer>();
for (int num : set1) {
if (set2.contains(num)) {
intersectionSet.add(num);
}
}
int[] intersection = new int[intersectionSet.size()];
int index = 0;
for (int num : intersectionSet) {
intersection[index++] = num;
}
return intersection;
}
}执行结果
通过
执行用时：4 ms，在所有 Java 提交中击败了21.31%的用户
内存消耗：38.7 MB，在所有 Java 提交中击败了28.49%的用户复杂度分析
时间复杂度：O( m+n )
空间复杂度：O( m+n ) Java方法二：排序 + 双指针
- 如果两个数组是有序的，则可以使用双指针的方法得到两个数组的交集。
- 首先对两个数组进行排序，然后使用两个指针遍历两个数组。
- 可以预见的是加入答案的数组的元素一定是递增的，为了保证加入元素的唯一性，我们需要额外记录变量
pre表示上一次加入答案数组的元素。 - 初始时，两个指针分别指向两个数组的头部。每
- 次比较两个指针指向的两个数组中的数字，如果两个数字不相等，则将指向较小数字的指针右移一位，如果两个数字相等，且该数字不等于
pre，将该数字添加到答案并更新pre变量，同时将两个指针都右移一位。 - 当至少有一个指针超出数组范围时，遍历结束。
代码
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
Arrays.sort(nums1);
Arrays.sort(nums2);
int length1 = nums1.length, length2 = nums2.length;
int[] intersection = new int[length1 + length2];
int index = 0, index1 = 0, index2 = 0;
while (index1 < length1 && index2 < length2) {
int num1 = nums1[index1], num2 = nums2[index2];
if (num1 == num2) {
// 保证加入元素的唯一性
if (index == 0 || num1 != intersection[index - 1]) {
intersection[index++] = num1;
}
index1++;
index2++;
} else if (num1 < num2) {
index1++;
} else {
index2++;
}
}
return Arrays.copyOfRange(intersection, 0, index);
}
}执行结果
通过
执行用时：1 ms，在所有 Java 提交中击败了99.93%的用户
内存消耗：38.8 MB，在所有 Java 提交中击败了8.99%的用户复杂度分析
时间复杂度：O( mlogm + nlogn )
空间复杂度：O( logm + logn )总结
- 今天是力扣算法题打卡的第五十二天！
- 文章采用
C#和Java两种编程语言进行解题 - 一些方法也是参考力扣大神写的，也是边学习边分享，再次感谢算法大佬们
- 那今天的算法题分享到此结束啦，明天再见！
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2021/10/13 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
