350. 两个数组的交集 II

解题思路

解法1--暴力解法

1.题目中说明了‘我们可以不考虑输出结果的顺序’，也就是说不考虑两个数组的顺序，只考虑包含关系
2.如果不考虑顺序，可以统计每个出现的数字的次数
3.如果长数组中包含短数组中的数字，然后输出相应次数（短数组中数字出现的次数与长数组中数字出现的次数做笔记）的此数字即可

解法2--使用哈希算法，考虑磁盘一次不可以全部读取

1.遍历nums1，将key为每个出现的数字，value为每个数字出现的次数，这里有一个技巧，可以先遍历nums1和nums2较短数组
2.遍历较长的数组，如果hashmap中已存在数字，则将其加入ans数组，并将出现的次数--，如果不存在则忽略

解法3--如果数组已排序，可以使用双指针解法

1.两个指针分别指向nums1、nums2头
2.开始遍历，如果遇到相等，则加入结果数组，并且i++、j++；如果不等，则将较小的元素指针++，直到一方遍历到尾，结束遍历

解题遇到的问题

1.错误的解法（考虑了原数组每个数字出现的顺序），留作‘纪念’，谨记之后做题，一定要认真审题

后续需要总结学习的知识点

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

##解法1
class Solution {
public static int[] intersect(int[] nums1, int[] nums2) {
        HashMap<Integer, Integer> nums2map = new HashMap<Integer, Integer>();
        HashMap<Integer, Integer> nums1map = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums2.length; i++) {
            if (nums2map.containsKey(nums2[i])) {
                nums2map.put(nums2[i], nums2map.get(nums2[i]) + 1);
            } else {
                nums2map.put(nums2[i], 1);
            }
        }

        for (int i = 0; i < nums1.length; i++) {
            if (nums1map.containsKey(nums1[i])) {
                nums1map.put(nums1[i], nums1map.get(nums1[i]) + 1);
            } else {
                nums1map.put(nums1[i], 1);
            }
        }

        if (nums1map.size() > nums2map.size()) {
            return realIntersect(nums2map, nums1map);
        } else {
            return realIntersect(nums1map, nums2map);
        }
    }

    private static int[] realIntersect(HashMap<Integer, Integer> shortNums,
            HashMap<Integer, Integer> longNums) {
        List<Integer> maxList = new ArrayList<Integer>();

        Iterator<Integer> it = shortNums.keySet().iterator();
        while (it.hasNext()) {
            int key = it.next();
            int value = shortNums.get(key);
            if (longNums.containsKey(key)) {
                int size = value > longNums.get(key)
                        ? longNums.get(key)
                        : value;
                for (int i = 0; i < size; i++) {
                    maxList.add(key);
                }
            }
        }

        int[] result = new int[maxList.size()];
        for (int i = 0; i < maxList.size(); i++) {
            result[i] = maxList.get(i);
        }
        return result;
    }
}

##解法2
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

class Solution {
    public static int[] intersect(int[] nums1, int[] nums2) {
        // 遍历nums1，将key为每个出现的数字，value为每个数字出现的次数，这里有一个技巧，可以先遍历nums1和nums2较短数组
        HashMap<Integer, Integer> numsmap = null;
        if (nums1.length > nums2.length) {
            numsmap = insertHashMap(nums2);
        } else {
            numsmap = insertHashMap(nums1);
        }

        // 遍历较长的数组，如果hashmap中已存在数字，则将其加入ans数组，并将出现的次数--，如果不存在则忽略
        if (nums1.length > nums2.length) {
            return getResult(numsmap, nums1);
        } else {
            return getResult(numsmap, nums2);
        }
    }

    public static int[] getResult(HashMap<Integer, Integer> numsmap,
            int[] nums) {
        List<Integer> ansIntegers = new ArrayList<Integer>();
        for (int i = 0; i < nums.length; i++) {
            if (numsmap.containsKey(nums[i])) {
                ansIntegers.add(nums[i]);
                if (numsmap.get(nums[i]) == 1) {
                    numsmap.remove(nums[i]);
                } else {
                    numsmap.put(nums[i], numsmap.get(nums[i]) - 1);
                }
            }
        }
        int[] ans = new int[ansIntegers.size()];
        for (int i = 0; i < ansIntegers.size(); i++) {
            ans[i] = ansIntegers.get(i);
        }
        return ans;
    }

    public static HashMap<Integer, Integer> insertHashMap(int[] nums) {
        HashMap<Integer, Integer> numsmap = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; i++) {
            numsmap.put(nums[i], numsmap.getOrDefault(nums[i], 0) + 1);
        }
        return numsmap;
    }

}

##解法3
class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int length1 = nums1.length, length2 = nums2.length;
        int[] intersection = new int[Math.min(length1, length2)];
        int index1 = 0, index2 = 0, index = 0;
        while (index1 < length1 && index2 < length2) {
            if (nums1[index1] < nums2[index2]) {
                index1++;
            } else if (nums1[index1] > nums2[index2]) {
                index2++;
            } else {
                intersection[index] = nums1[index1];
                index1++;
                index2++;
                index++;
            }
        }
        return Arrays.copyOfRange(intersection, 0, index);
    }
}

##错误的解法（考虑了原数组每个数字出现的顺序）
class Solution {
    public static int[] intersect(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) {
            return realIntersect(nums2, nums1);
        } else {
            return realIntersect(nums1, nums2);
        }
    }

    private static int[] realIntersect(int[] shortNums, int[] longNums) {
        List<Integer> maxList = new ArrayList<Integer>();
        for (int i = 0; i < longNums.length; i++) {
            int k = i;
            List<Integer> list = new ArrayList<Integer>();
            for (int j = 0; j < shortNums.length; j++) {
                if (k < longNums.length && shortNums[j] == longNums[k]) {
                    k++;
                    list.add(shortNums[j]);
                }
            }
            if (k > i && list.size() > maxList.size()) {
                maxList = list;
            }
        }

        int[] result = new int[maxList.size()];
        for (int i = 0; i < maxList.size(); i++) {
            result[i] = maxList.get(i);
        }
        return result;
    }
}