前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【算法千题案例】⚡️每日LeetCode打卡⚡️——52.两个数组的交集

【算法千题案例】⚡️每日LeetCode打卡⚡️——52.两个数组的交集

作者头像
呆呆敲代码的小Y
发布2021-10-15 15:07:56
3860
发布2021-10-15 15:07:56
举报
文章被收录于专栏:呆呆敲代码的小Y 公众号

请添加图片描述
请添加图片描述

原题样例:两个数组的交集

给定两个数组,编写一个函数来计算它们的交集。

示例:

代码语言:javascript
复制
输入:nums1 = [1,2,2,1], nums2 = [2,2]
输出:[2]

示例 2:

代码语言:javascript
复制
输入:nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出:[9,4]
代码语言:javascript
复制
输出结果中的每个元素一定是唯一的。
我们可以不考虑输出结果的顺序。

????C#方法:排序

  • 计算两个数组的交集,直观的方法是遍历数组 nums1,对于其中的每个元素,遍历数组 nums2 判断该元素是否在数组 nums2 中,如果存在,则将该元素添加到返回值。
  • 假设数组 nums1 和 nums2 的长度分别是 m和 n,则遍历数组 nums1 需要 O(m) 的时间,判断 nums1 中的每个元素是否在数组 nums2 中需要 O(n) 的时间,因此总时间复杂度是O(mn)。
  • 如果使用哈希集合存储元素,则可以在O(1) 的时间内判断一个元素是否在集合中,从而降低时间复杂度。
  • 首先使用两个集合分别存储两个数组中的元素,然后遍历较小的集合,判断其中的每个元素是否在另一个集合中,如果元素也在另一个集合中,则将该元素添加到返回值。
  • 该方法的时间复杂度可以降低到 O(m+n)

代码:

代码语言:javascript
复制
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;
    }
}

执行结果

代码语言:javascript
复制
通过
执行用时: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)

代码:

代码语言:javascript
复制
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;
    }
}

执行结果

代码语言:javascript
复制
通过
执行用时:4 ms,在所有 Java  提交中击败了21.31%的用户
内存消耗:38.7 MB,在所有 Java 提交中击败了28.49%的用户

复杂度分析

代码语言:javascript
复制
时间复杂度:O( m+n )
空间复杂度:O( m+n ) 

Java方法二:排序 + 双指针

  • 如果两个数组是有序的,则可以使用双指针的方法得到两个数组的交集。
  • 首先对两个数组进行排序,然后使用两个指针遍历两个数组。
  • 可以预见的是加入答案的数组的元素一定是递增的,为了保证加入元素的唯一性,我们需要额外记录变量 pre 表示上一次加入答案数组的元素。
  • 初始时,两个指针分别指向两个数组的头部。每
  • 次比较两个指针指向的两个数组中的数字,如果两个数字不相等,则将指向较小数字的指针右移一位,如果两个数字相等,且该数字不等于pre,将该数字添加到答案并更新 pre 变量,同时将两个指针都右移一位。
  • 当至少有一个指针超出数组范围时,遍历结束。

代码

代码语言:javascript
复制
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);
    }
}

执行结果

代码语言:javascript
复制
通过
执行用时:1 ms,在所有 Java  提交中击败了99.93%的用户
内存消耗:38.8 MB,在所有 Java 提交中击败了8.99%的用户

复杂度分析

代码语言:javascript
复制
时间复杂度:O( mlogm + nlogn )
空间复杂度:O( logm + logn )

总结

  • 今天是力扣算法题打卡的第五十二天!
  • 文章采用 C#Java 两种编程语言进行解题
  • 一些方法也是参考力扣大神写的,也是边学习边分享,再次感谢算法大佬们
  • 那今天的算法题分享到此结束啦,明天再见!
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2021/10/13 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • ????C#方法:排序
  • Java 方法:两个集合
  • Java方法二:排序 + 双指针
  • 总结
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档