​LeetCode刷題實戰350：兩個數組的交集 II

算法的重要性，我就不多說了吧，想去大廠，就必須要經過基礎知識和業務邏輯面試+算法面試。是以，為了提高大家的算法能力，這個公衆号後續每天帶大家做一道算法題，題目就從LeetCode上面選 ！

今天和大家聊的問題叫做 兩個數組的交集 II，我們先來看題面：

https://leetcode-cn.com/problems/interp-of-two-arrays-ii/

Given two integer arrays nums1 and nums2, return an array of their interp. Each element in the result must appear as many times as it shows in both arrays and you may return the result in any order.

給定兩個數組，編寫一個函數來計算它們的交集。

示例

示例 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 的元素存儲在磁盤上，記憶體是有限的，并且你不能一次加載所有的元素到記憶體中，你該怎麼辦？
           

解題

用Map來建立nums1中字元和其出現個數之間的映射, 然後周遊nums2數組，如果目前字元在Map中的個數大于0，則将此字元加入結果res中，然後Map的對應值自減1。

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

    List<Integer> tmp = new ArrayList<>();

    Map<Integer, Integer> map = new HashMap<Integer, Integer>();

    for (int i = 0; i < nums1.length; i++) {
        Integer value = map.get(nums1[i]);
        map.put(nums1[i], (value == null ? 0 : value) + 1);
    }

    for (int i = 0; i < nums2.length; i++) {
        if (map.containsKey(nums2[i]) && map.get(nums2[i]) != 0) {
            tmp.add(nums2[i]);
            map.put(nums2[i], map.get(nums2[i]) - 1);
        }
    }

    int[] result = new int[tmp.size()];
    int i = 0;
    for (Integer e : tmp)
        result[i++] = e;
    return result;
}
}
           

好了，今天的文章就到這裡，如果覺得有所收獲，請順手點個在看或者轉發吧，你們的支援是我最大的動力 。

上期推文：

LeetCode1-340題彙總，希望對你有點幫助！

LeetCode刷題實戰341：扁平化嵌套清單疊代器

LeetCode刷題實戰342：4的幂

LeetCode刷題實戰343：整數拆分

LeetCode刷題實戰344：反轉字元串

LeetCode刷題實戰345：反轉字元串中的元音字母

LeetCode刷題實戰346：資料流中的移動平均值

LeetCode刷題實戰347：前 K 個高頻元素

LeetCode刷題實戰348：設計井字棋

LeetCode刷題實戰349：兩個數組的交集