<jupyter_start><jupyter_text>两个数组的交集 II* Slug: intersection-of-two-arrays-ii* Date: 2018-06-26* Category: LeetCode* Tags: 数组, 算法* Author: timking* Summary: LeetCode - 探索 - 初级算法 > [原文链接](https://leetcode-cn.com/problems/intersection-of-two-arrays-ii/description/) 给定两个数组，写一个方法来计算它们的交集。例如: 给定 nums1 = [1, 2, 2, 1], nums2 = [2, 2], 返回 [2, 2].**注意：*** 输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。      * 我们可以不考虑输出结果的顺序。**跟进:*** 如果给定的数组已经排好序呢？你将如何优化你的算法？    * 如果 nums1 的大小比 nums2 小很多，哪种方法更优？        * 如果nums2的元素存储在磁盘上，内存是有限的，你不能一次加载所有的元素到内存中，你该怎么办？  初步解答首先先考虑如何实现这个算法。从题目看是要求返回交集数组，需要注意的地方题目也已经给标注出来了。这边不要求输出结果顺序，所以比较简单。因为要求交集元素保留在结果数组中的次数，所以 set 结构无疑是不适用的。一开始想到利用数组的特性来做，得出以下代码：<jupyter_code>class Solution:
    def intersect(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        ret = []
        rng = nums1
        in_arr = nums2
        if len(nums1) < len(nums2):
            rng = nums2
            in_arr = nums1
        for i in rng:
            if i in in_arr:
                ret.append(i)
                in_arr.remove(i)
        return ret<jupyter_output><empty_output><jupyter_text>但是这样做有个缺点，在一个未排序的数组中，判断是否存在 `in` 和 `remove` 操作复杂度都为 `O(n)`, 这将会带来额外开销。所以，其实这个算法在数据量比较大的情况下是不适用的。  优化这边就按给定的跟进思路来继续优化。如果给定的数组是已经优化好的呢，或者一个数组要比另一个数组小的多。从这一点上考虑，假定是排序好的数组，可以通过比较两个数组相同下标的值来判断，如果存在下标不等的情况则其中一个数组下标前移。根据这个思路，写出以下代码：<jupyter_code>class Solution:
    def intersect(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        nums1.sort()
        nums2.sort()
        
        ret = []
        i = 0
        j = 0
        while i < len(nums1) and j < len(nums2):
            z = nums1[i] - nums2[j]
            if z == 0:
                ret.append(nums1[i])
                i += 1
                j += 1
            elif z > 0:
                j += 1
            else:
                i += 1
        return ret<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.12330827067669173, 'fraction_numerical': 0.02506265664160401, 'mean_word_length': 2.2828947368421053, 'pattern_counts': {'":': 0, '<': 12, '<?xml version=': 0, '>': 11, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '572301', 'license': 'MIT', 'n_tokens_mistral': 1087, 'n_tokens_neox': 1134, 'n_words': 134, 'path': 'content/LeetCode/intersection-of-two-arrays-ii/main.ipynb', 'repo_name': 'TimKingNF/timking.github.io', 'size': '1995'}