349.两个数组的交集 🟩

题目

LeetCode 简单

题目

给定两个数组 nums1 和 nums2 ，返回它们的交集。输出结果中的每个元素一定是唯一的。我们可以 不考虑输出结果的顺序 。

示例：
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的

题解

方法：集合Set

复杂度

时间复杂度：O(m+n)

其中 m 和 n 分别是两个数组的长度。使用两个集合分别存储两个数组中的元素需要 O(m+n) 的时间，遍历较小的集合并判断元素是否在另一个集合中需要 O(min(m,n)) 的时间，因此总时间复杂度是 O(m+n)。

空间复杂度：O(m+n)

其中 m 和 n 分别是两个数组的长度。空间复杂度主要取决于两个集合。

function intersection(nums1, nums2) {
  let resSet = new Set(),
    nums1Set = new Set(nums1)
  for (let i of nums2) {
    if (nums1Set.has(i)) {
      resSet.add(i)
    }
  }
  return Array.from(resSet)

  //简化
  // return [...new Set(nums1.filter(item => nums2.includes(item)))]
}

const nums1 = [4, 9, 5]
const nums2 = [9, 4, 9, 8, 4]
console.log('🌰', intersection(nums1, nums2))

执行结果

🌰 [ 9, 4 ]

方法：排序 + 双指针

复杂度

时间复杂度：O(mlogm+nlogn)

其中 m 和 n 分别是两个数组的长度。对两个数组排序的时间复杂度分别是 O(mlogm) 和 O(nlogn)，双指针寻找交集元素的时间复杂度是 O(m+n)，因此总时间复杂度是 O(mlogm+nlogn)。

空间复杂度：O(logm+logn)

其中 m 和 n 分别是两个数组的长度。空间复杂度主要取决于排序使用的额外空间。

function intersectionUseTwoPointers(nums1, nums2) {
  nums1.sort((a, b) => a - b)
  nums2.sort((a, b) => a - b)

  let i1 = 0,
    i2 = 0,
    result = []
  while (i1 < nums1.length && i2 < nums2.length) {
    if (nums1[i1] === nums2[i2]) {
      if (result.indexOf(nums1[i1]) === -1) {
        result.push(nums1[i1])
      }
      i1++
      i2++
    }
    if (nums1[i1] < nums2[i2]) {
      i1++
    }
    if (nums1[i1] > nums2[i2]) {
      i2++
    }
  }
  return result
}

const nums1 = [1, 2, 2, 1],
  nums2 = [2, 2]
console.log('🌰', intersectionUseTwoPointers(nums1, nums2))

执行结果

🌰 [ 2 ]

本页目录