🌗 350. 两个数组的交集 II

难度: 🌗

• 问题描述
• 解法
• 输出
• 进阶

问题描述

---

解法

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        // 思路：
        // 先遍历小数组
        // 遍历大数组
        int m = nums1.length;
        int n = nums2.length;
        HashMap<Integer, Integer> map = new HashMap<>();
        List<Integer> list = new ArrayList<>();
        if(m <= n) {
            for(int i : nums1) {
                if(!map.containsKey(i)) {
                    map.put(i, 1);
                } else {
                    int count = map.get(i);
                    count ++;
                    map.put(i, count);
                }
            }
            for(int j : nums2) {
                if(map.containsKey(j)) {
                    list.add(j);
                    int count = map.get(j);
                    count --;
                    if(count == 0) {
                        map.remove(j);
                    } else {
                        map.put(j, count);
                    }
                    if(map.isEmpty()) {
                        return getRes(list);
                    }
                }
            }
        } else {
            for(int i : nums2) {
                if(!map.containsKey(i)) {
                    map.put(i, 1);
                } else {
                    int count = map.get(i);
                    count ++;
                    map.put(i, count);
                }
            }
            for(int j : nums1) {
                if(map.containsKey(j)) {
                    list.add(j);
                    int count = map.get(j);
                    count --;
                    if(count == 0) {
                        map.remove(j);
                    } else {
                        map.put(j, count);
                    }
                    if(map.isEmpty()) {
                        return getRes(list);
                    }
                } 
            }
        }
        return getRes(list);
    }

    private int[] getRes(List<Integer> list) {
        int len = list.size();
        int[] res = new int[len];
        for(int i = 0; i < len; i ++) {
            res[i] = list.get(i);
        }
        return res;
    }
}

---

输出

---

进阶

1. 若给定是数组已经排好序
   • 双指针 O(N)
2. 若 nums1.length < nums2.length
   • 采用 HashMap 的过程中，map 存放的是小数组，然后遍历大数组查询是否存在
3. 若 nums2 过大，存在磁盘上
   • 采用 HashMap 存放 nums1，每次从 nums2 中取部分元素进行查询
4. 若 nums1 & nums2 均过大，均存在磁盘上
   • 采用 归并排序，每次分别排序 一部分的 nums1 & nums2，放到小文件中
   • 然后从 小文件中合并为 排序好的 nums1 & nums2
   • 双指针排序 nums1 & nums2