349. 两个数组的交集 & 350. 两个数组的交集 II(数组)【S】

349. 两个数组的交集

本文主要是进行刷题记录,方便日后查看,参考的文章都在最后的参考链接中。
在这里插入图片描述

题目本身并不难,但是可能会考察多种解法。每一种解法的原理都不大相似

1. 辅助空间

根据题目可以发现,我们需要找到所有在两个数组中都出现的数字,且需要将结果去重。

去重,最先想到的就是hashset,能够保证结果的唯一性——所以hashset就是用来去重的。

所以,我们将两个数组都存放到hashset中,第一个hashset是无脑将nums1数组全部丢进去;第二个hashset是先判断该数字在第一个哈希集合中是否存在,存在才放入,来去重。最后将第二个hashset遍历即可

(hashmap和hashset的方法类似,稍微记忆即可使用了)

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        HashSet<Integer>first = new HashSet<>();
        HashSet<Integer>second = new HashSet<>();
        for(int i: nums1){
            first.add(i);
        }
        for(int i: nums2){
            if(first.contains(i)){		// 包含在first中存在的结点才加入,不存在的没有必要了
                second.add(i);
            }
        }
        int[] res = new int[second.size()];
        int i = 0;
        for(Integer num: second){
            res[i++] = num;
        }
        return res;
    }
}

——时间复杂度O(N),空间复杂度O(N+M)

2. 排序 + 双指针

前面是拿空间换时间,下面拿时间换空间。先将数组排序,然后分别用一个指针开始遍历比较

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int i = 0, j = 0;
        HashSet<Integer>set = new HashSet<>();
        while(i < nums1.length && j < nums2.length){
            if(nums1[i] == nums2[j]){
                set.add(nums2[j]);
                i++;
                j++;
            }
            else if(nums1[i] < nums2[j]) i++;
            else if(nums1[i] > nums2[j]) j++;
        }
        int[] res = new int[set.size()];
        i = 0;
        for(Integer num: set){
            res[i++] = num;
        }
        return res;
    }
}

——时间复杂度O(NlogN),空间复杂度O(N)

3. 排序 + 二分查找

——主要是复习二分查找的写法,性能不是很好,每个结点都需要去O(logN)的时间复杂度去查找

class Solution {
    private boolean binarySearch(int[] nums, int target, int left, int right){
        if(left > right) return false;
        int mid = left + (right - left) / 2;
        if(nums[mid] == target) return true;        // 表示存在
        else if(nums[mid] > target) return binarySearch(nums, target, left, mid - 1);
        else return binarySearch(nums, target, mid + 1, right);
    }
    public int[] intersection(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        HashSet<Integer>set = new HashSet<>();
        for(int num: nums2){
            if(binarySearch(nums1, num, 0, nums1.length - 1)){
                set.add(num);
            }
        }
        int[] res = new int[set.size()];
        int i = 0;
        for(Integer num: set){
            res[i++] = num;
        }
        return res;
    }
}

——代码的重点就是写对二分查找,关注的就是边界条件是否正确(我用了递归的形式,这个非典型且没必要),如下是常见的写法:

private boolean binarySearch(int[] nums, int target){
    int left = 0, right = nums.length - 1;
    while(left <= right){
        int mid = left + (right - left) / 2;
        if(nums[mid] == target) return true;
        else if(nums[mid] > target) right = mid - 1;
        else left = mid + 1;
    }
    return false;
}

参考:

  1. https://leetcode-cn.com/problems/intersection-of-two-arrays/solution/duo-chong-jie-fa-jie-jue-349-liang-ge-shu-zu-de-ji/

350. 两个数组的交集 II

在这里插入图片描述
本题和上题的不同在于:本题是数组元素可以重复,那么哈希集合就不大适合了,更适合的是下面的两种基于排序的方法。

本题的关键在于进阶的问题。

首先先实现:

排序 + 双指针

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int i = 0, j = 0;
        List<Integer>temp = new ArrayList<>();
        while(i < nums1.length && j < nums2.length){
            if(nums1[i] == nums2[j]){
                temp.add(nums2[j]);
                i++; 
                j++;
            }
            else if(nums1[i] < nums2[j]) i++;
            else if(nums1[i] > nums2[j]) j++;
        }
        int[] res = new int[temp.size()];
        i = 0;
        for(Integer num: temp){
            res[i++] = num;
        }
        return res;
    }
}

——进阶1的解答,如果数组已经排好序了,那么就双指针遍历即可

——时间复杂度O(N),不计入排序时间

进阶2:如果一个数组很短,那么将它排好序,然后用长数组遍历在短数组中查找,查找方式是二分查找法。

官方题解1,还给出了哈希表的解法:key-value记录的是num值和出现的次数:

  • nums1遍历,将所有数字都存放到哈希表中,key:数字;value:出现的次数
  • nums2遍历,看每个数字是否在哈希表中出现,出现就添加,并且对应的次数–

当数组比较大时,无法进行排序,那么适合用哈希表的方法

但是我觉得这个回答更好:如果内存十分小,不足以将数组全部载入内存,那么必然也不能使用哈希这类费空间的算法。归并排序是天然适合外部排序的算法,可以将分割后的子数组写到单个文件中,归并时将小文件合并为更大的文件。当两个数组均排序完成生成两个大文件后,即可使用双指针遍历两个文件,如此可以使空间复杂度最低。

参考:

  1. https://leetcode-cn.com/problems/intersection-of-two-arrays-ii/solution/liang-ge-shu-zu-de-jiao-ji-ii-by-leetcode-solution/
  2. https://leetcode-cn.com/problems/intersection-of-two-arrays-ii/solution/jin-jie-san-wen-by-user5707f/