侧边栏壁纸
博主头像
Wyatt博主等级

Done is better than perfect!

  • 累计撰写 103 篇文章
  • 累计创建 31 个标签
  • 累计收到 7 条评论

01|俩个数组交集(350)

Wyatt
2020-10-12 / 0 评论 / 0 点赞 / 301 阅读 / 3,089 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2020-12-03,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

1.题目

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

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

说明:

输出结果中每个元素出现的次数,应与元素在两个数组中出现次数的最小值一致。
我们可以不考虑输出结果的顺序。

进阶:

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

2.题解

初次做题,通过各种讲解,个人获取到到办法是通过映射办法(map映射)来解决。因为我们需要找出俩个数组到交集,同时应该与俩个数组中出现的最低次数一致。我们就必须统计每个值出现的次数,因此我们的映射关系就成了<元素,次数>。

3.答案分析

3.1 Code

class Solution {
   public int[] intersect(int[] nums1, int[] nums2) {
        int[] temp = {};
        if (nums1.length > nums2.length) {
            //nums1 与 nums2交换
            temp = nums1;
            nums1 = nums2;
            nums2 = temp;
        }
        Map<Integer, Integer> result = new HashMap<Integer, Integer>();
        for (int n : nums1
        ) {
            int count = result.getOrDefault(n, 0) + 1;
            result.put(n, count);
        }
        int[] intersection = new int[nums1.length];
        int index = 0;
        for (int num : nums2) {
            int count = result.getOrDefault(num, 0);
            if (count > 0) {
                intersection[index++] = num;
                count--;
                if (count > 0) {
                    result.put(num, count);
                } else {
                    result.remove(num);
                }
            }
        }
        return Arrays.copyOfRange(intersection, 0, index);

    }

}

简单问题,相对容易。初次写,效率略低。
个人写的性能一般

3.2 复杂度分析

  • 时间复杂度:O(m+n),m和n代表俩个数组的长度。
  • 空间复杂度:O(min(m,n)),返回new int[nums1.length]取值为最小长度的数组。

4.进阶分析

4.1 重构

进阶问题是数组已经排好序,那么我们可以优化一下我们的算法。参考他人方法,此处我们可以使用“双指针”解法。
举例子:nums1=[2,3,7,9],nums2=[2,4,6,7]
|2|3 |7 |9 |
|-------|-------|-------|--|--|
|2|4|6|7|

4.2 思路

设定俩个0开始的指针(index1,index2),比较这俩个指针所在的(nums1,nums2)的元素是否相等。

  1. 如果俩元素相等,则将相同元素放到空白数组。并且index1,index2均向后移一位
  2. 如果俩元素不相同,那么小的指针向后移。
  3. 循环上面步骤
  4. 直到任意一个数组结束

4.3 优化

对于需要判断哪个数组长度问题,我们可以通过交换数组的方式,来让nums1始终为最小数组。

5.进阶答案分析

5.1 Code

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {


        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int length1 = nums1.length;
        int length2 = nums2.length;
        if (length1 > length2) {
            return intersect(nums2, nums1);
        }
        int index = 0;
        int index1 = 0;
        int index2 = 0;
        int[] result = new int[length1];
        while (index1 < length1 && index2 < length2) {
            if (nums1[index1] < nums2[index2]) {
                index1++;
            } else if (nums1[index1] > nums2[index2]) {
                index2++;
            } else {
                result[index] = nums1[index1];
                index1++;
                index2++;
                index++;
            }
        }
        return Arrays.copyOfRange(result, 0, index);

    }
}

效率还是略低

5.2 复杂度分析

  • 时间复杂度:O(mlogm+nlogn),对两个数组进行排序的时间复杂度是 O(mlogm+nlogn),遍历两个数组的时间复杂度是 O(m+n),因此总时间复杂度是O(mlogm+nlogn)
  • 空间复杂度:O(min(m,n)),返回new int[nums1.length]取值为最小长度的数组。

6.总结

从这第一次做题中,花费了我蛮多的时间去审题和编写。但是从我的第一题,我学到了几个知识点:

  • map映射
  • 双指标解法
  • 递归来交换数组
0

评论区