LeetCode刷题之350.两个数组的交集 II

LeetCode刷题之350.两个数组的交集 II

我不知道将去向何方，但我已在路上！

时光匆匆，虽未曾谋面，却相遇于斯，实在是莫大的缘分，感谢您的到访 ！

• 题目：
  给定两个数组，编写一个函数来计算它们的交集。
• 示例：

示例 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的元素存储在磁盘上，磁盘内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？
• 代码1：

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        a = []
        if len(nums1) > len(nums2):
            for num in nums2:
                if num in nums1:
                    a.append(num)
                    nums1.remove(num)
        else:
            for num in nums1:
                if num in nums2:
                    a.append(num)
                    nums2.remove(num)
        return(a)
# 执行用时 :160 ms, 在所有 Python3 提交中击败了5.78%的用户
# 内存消耗 :13.9 MB, 在所有 Python3 提交中击败了5.06%的用户

• 算法说明：
  建立一个空的列表a，判断两个数组的长度，如果len(nums1) > len(nums2)，用长度较小nums2中的元素和另一个数组nums1进行比对，如果有相同的元素num，将该元素存储到a中，然后将该元素从较长的数组nums1中删除；反之亦然；返回a即可。
• 代码2：

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        nums1.sort()
        nums2.sort()
        a = []
        i,j = 0,0
        while(i < len(nums1) and j < len(nums2)):
            if nums1[i] == nums2[j]:
                a.append(nums1[i])
                i = i + 1
                j = j + 1
            elif nums1[i] < nums2[j]:
                i += 1
            elif nums1[i] > nums2[j]:
                j += 1
        return a
# 执行用时 :76 ms, 在所有 Python3 提交中击败了62.97%的用户
# 内存消耗 :13.8 MB, 在所有 Python3 提交中击败了5.06%的用户

• 算法说明：
  先将两个数组，进行排序，建立一个空列表a；建立两个指针i和j分别指向nums1和nums2，如果当前指针所指的元素相等，则将元素存储到a中；否则，判断两个指针所指元素的大小，将数值较小的一个指针后移一位；一直循环到，任意一个指针指向数组的最后。