两个数组的交集，O(n)，就地，只有恒定数量的额外内存

基础概念

两个数组的交集是指两个数组中共有的元素组成的集合。通常情况下，我们需要找出两个数组中都存在的元素，并且结果中每个元素只出现一次。

相关优势

• 时间复杂度：O(n)的时间复杂度意味着算法在处理大数据集时效率很高。
• 空间复杂度：只使用恒定数量的额外内存，意味着算法的空间效率也很高。

类型

• 暴力解法：通过两层循环遍历两个数组，时间复杂度为O(n^2)，不满足题目要求。
• 哈希表：使用哈希表存储一个数组的元素，然后遍历另一个数组检查元素是否在哈希表中，时间复杂度为O(n)，但需要额外的空间。
• 双指针：如果两个数组已经排序，可以使用双指针方法找到交集，时间复杂度为O(n)，且只需要恒定数量的额外空间。

应用场景

• 数据分析：在数据分析中，经常需要找出多个数据集中的共同特征或元素。
• 推荐系统：在推荐系统中，可能需要找出用户之间的共同兴趣点。
• 数据库查询优化：在数据库查询中，可以通过找出多个表的交集来优化查询结果。

问题与解决方案

假设我们有两个已排序的数组nums1和nums2，我们需要找到它们的交集，并且要求空间复杂度为O(1)（即就地操作）。

问题

如何在不使用额外空间的情况下，找到两个已排序数组的交集？

原因

如果数组未排序，直接找交集通常需要使用哈希表，这会引入额外的空间复杂度。即使是已排序的数组，直接使用双指针法也需要额外的空间来存储结果。

解决方案

我们可以使用双指针法，并且在原数组上进行操作，以满足空间复杂度为O(1)的要求。具体步骤如下：

1. 初始化两个指针i和j分别指向nums1和nums2的起始位置。
2. 初始化一个变量k用于记录结果数组的位置。
3. 比较nums1[i]和nums2[j]：
   • 如果相等，则将该元素放入结果数组，并移动两个指针。
   • 如果nums1[i]小于nums2[j]，则移动指针i。
   • 如果nums1[i]大于nums2[j]，则移动指针j。

• 重复步骤3，直到任一数组遍历完毕。

示例代码

def intersect(nums1, nums2):
    i, j = 0, 0
    k = 0
    while i < len(nums1) and j < len(nums2):
        if nums1[i] == nums2[j]:
            # 避免重复元素
            if k == 0 or nums1[k-1] != nums1[i]:
                nums1[k] = nums1[i]
                k += 1
            i += 1
            j += 1
        elif nums1[i] < nums2[j]:
            i += 1
        else:
            j += 1
    return nums1[:k]

# 示例
nums1 = [1, 2, 2, 1]
nums2 = [2, 2]
print(intersect(nums1, nums2))  # 输出: [2, 2]

参考链接

LeetCode 350. 两个数组的交集 II

通过上述方法，我们可以在O(n)的时间复杂度和O(1)的空间复杂度内找到两个已排序数组的交集。