兩個(gè)數(shù)組的交集

給定兩個(gè)數(shù)組袋励，編寫一個(gè)函數(shù)來計(jì)算它們的交集王滤。

示例 1：

輸入：nums1 = [1,2,2,1], nums2 = [2,2]
輸出：[2]

示例 2：

輸入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
輸出：[9,4]

說明：

• 輸出結(jié)果中的每個(gè)元素一定是唯一的。
• 我們可以不考慮輸出結(jié)果的順序晶衷。

方法一：Set+逐一判斷

public int[] intersection(int[] nums1, int[] nums2) {
    Set<Integer> set = new HashSet<>();
    Set<Integer> intersectionSet = new HashSet<>();
    for (int num : nums1) {
        set.add(num);
    }
    for (int num : nums2) {
        if (set.contains(num)) {
            intersectionSet.add(num);
        }
    }
    int[] res = new int[intersectionSet.size()];
    int i = 0;
    for (Integer num : intersectionSet) {
        res[i++] = num;
    }
    return res;
}

方法二：排序+雙指針

首先對(duì)兩個(gè)數(shù)組進(jìn)行排序壮虫，然后使用兩個(gè)指針遍歷兩個(gè)數(shù)組「』梗可以預(yù)見的是加入答案的數(shù)組的元素一定是遞增的桑孩，為了保證加入元素的唯一性拜鹤，我們需要額外記錄變量 pre 表示上一次加入答案數(shù)組的元素。

初始時(shí)流椒，兩個(gè)指針分別指向兩個(gè)數(shù)組的頭部敏簿。每次比較兩個(gè)指針指向的兩個(gè)數(shù)組中的數(shù)字，如果兩個(gè)數(shù)字不相等宣虾，則將指向較小數(shù)字的指針右移一位惯裕，如果兩個(gè)數(shù)字相等，且該數(shù)字不等于 pre 绣硝，將該數(shù)字添加到答案并更新pre 變量蜻势，同時(shí)將兩個(gè)指針都右移一位。當(dāng)至少有一個(gè)指針超出數(shù)組范圍時(shí)鹉胖，遍歷結(jié)束握玛。

public int[] intersection(int[] nums1, int[] nums2) {
    Arrays.sort(nums1);
    Arrays.sort(nums2);
    int[] temp = new int[nums1.length + nums2.length];
    int i = 0, j = 0, k = 0;
    while (i < nums1.length && j < nums2.length) {
        if (nums1[i] == nums2[j]) {
            // 保證元素不重復(fù)
            if (k == 0 || temp[k - 1] != nums1[i]) {
                temp[k++] = nums1[i];
            } 
            i++;
            j++;
        } else if (nums1[i] < nums2[j]) {
            i++;
        } else {
            j++;
        }
    }
    int[] res = new int[k];
    System.arraycopy(temp, 0, res, 0, k);
    return res;
}

兩個(gè)數(shù)組的交集 II

給定兩個(gè)數(shù)組够傍，編寫一個(gè)函數(shù)來計(jì)算它們的交集。

示例 1：

輸入：nums1 = [1,2,2,1], nums2 = [2,2]
輸出：[2,2]

示例 2:

輸入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
輸出：[4,9]

說明：

• 輸出結(jié)果中每個(gè)元素出現(xiàn)的次數(shù)挠铲，應(yīng)與元素在兩個(gè)數(shù)組中出現(xiàn)次數(shù)的最小值一致冕屯。
• 我們可以不考慮輸出結(jié)果的順序。

進(jìn)階：

• 如果給定的數(shù)組已經(jīng)排好序呢市殷？你將如何優(yōu)化你的算法愕撰？
• 如果 nums1的大小比 nums2小很多，哪種方法更優(yōu)醋寝？
• 如果 nums2的元素存儲(chǔ)在磁盤上搞挣，內(nèi)存是有限的，并且你不能一次加載所有的元素到內(nèi)存中音羞，你該怎么辦囱桨？

方法一：Map

之所以要記錄在nums1中出現(xiàn)的次數(shù)，是因?yàn)樵趎um2中同一個(gè)數(shù)字的出現(xiàn)次數(shù)可能比nums1多嗅绰，也可能更少

public int[] intersect(int[] nums1, int[] nums2) {
    Map<Integer, Integer> map = new HashMap<>();
    int[] temp = new int[nums1.length + nums2.length];
    for (int num : nums1) {
        map.put(num, map.getOrDefault(num, 0) + 1);
    }
    int i = 0;
    for (int num : nums2) {
        if (map.get(num) != null && map.get(num) > 0) {
            temp[i++] = num;
            map.put(num, map.get(num) - 1);
        }
    }
    int[] res = new int[i];
    System.arraycopy(temp, 0, res, 0, i);
    return res;
}

方法二：排序

與之前的相比只是不需要進(jìn)行重復(fù)的判斷

public int[] intersect(int[] nums1, int[] nums2) {
    public int[] intersect(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int[] temp = new int[nums1.length + nums2.length];
        int i = 0, j = 0, k = 0;
        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] == nums2[j]) {
                temp[k++] = nums1[i];
                i++;
                j++;
            } else if (nums1[i] < nums2[j]) {
                i++;
            } else {
                j++;
            }
        }
        int[] res = new int[k];
        System.arraycopy(temp, 0, res, 0, k);
        return res;
    }
}