我正在参与「启航方案」

题目

给定两个数组 nums1 和 nums2，回来 它们的交集 。输出成果中的每个元素一定是 唯一 的。咱们能够 不考虑输出成果的次序 。

示例 1：

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

示例 2：

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

办法一：两个调集

思路及解法

计算两个数组的交集，直观的办法是遍历数组 nums1，对于其间的每个元素，遍历数组 nums2 判别该元素是否在数组 nums2 中，假如存在，则将该元素添加到回来值。假设数组 nums1 和 nums2 的长度别离是 $m$ 和 $n$，则遍历数组 nums1 需求 $O(m)$ 的时刻，判别 nums1 中的每个元素是否在数组 nums2 中需求 $O(n)$ 的时刻，因而总时刻复杂度是 $O(mn)$。

假如运用哈希调集存储元素，则能够在 $O(1)$ 的时刻内判别一个元素是否在调集中，从而降低时刻复杂度。

首要运用两个调集别离存储两个数组中的元素，然后遍历较小的调集，判别其间的每个元素是否在另一个调集中，假如元素也在另一个调集中，则将该元素添加到回来值。该办法的时刻复杂度能够降低到 $O(m+n)$

代码

class Solution {
    func intersection(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
        return set_intersection(Set(nums1), Set(nums2))
    }
    func set_intersection(_ set1: Set<Int>, _ set2: Set<Int>) -> [Int] {
        if set1.count > set2.count {
            return set_intersection(set2, set1)
        }
        var intersection: [Int] = []
        for num in set1 {
            if set2.contains(num) {
                intersection.append(num)
            }
        }
        return intersection
    }
}

复杂度剖析

• 时刻复杂度：$O(m+n)$，其间 $m$ 和 $n$ 别离是两个数组的长度。运用两个调集别离存储两个数组中的元素需求 $O(m+n)$ 的时刻，遍历较小的调集并判别元素是否在另一个调集中需求 $O(\min (m,n))$ 的时刻，因而总时刻复杂度是 $O(m+n)$。

• 空间复杂度：$O(m+n)$，其间 $m$ 和 $n$ 别离是两个数组的长度。空间复杂度首要取决于两个调集

办法二：排序 + 双指针

思路及解法

假如两个数组是有序的，则能够运用双指针的办法得到两个数组的交集。

首要对两个数组进行排序，然后运用两个指针遍历两个数组。能够预见的是参加答案的数组的元素一定是递加的，为了确保参加元素的唯一性，咱们需求额定记录变量 $\text{pre}$ 表示上一次参加答案数组的元素。

初始时，两个指针别离指向两个数组的头部。每次比较两个指针指向的两个数组中的数字，假如两个数字不相等，则将指向较小数字的指针右移一位，假如两个数字相等，且该数字不等于 $\text{pre}$ ，将该数字添加到答案并更新 $\text{pre}$ 变量，一起将两个指针都右移一位。当至少有一个指针超出数组范围时，遍历结束。

代码

class Solution {
    func intersection(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
        let newNums1: [Int] = nums1.sorted()
        let newNums2: [Int] = nums2.sorted()
        let length1: Int = newNums1.count
        let length2: Int = newNums2.count
        var intersection: [Int] = []
        var index1 = 0
        var index2 = 0
        while index1 < length1 && index2 < length2 {
            let num1 = newNums1[index1]
            let num2 = newNums2[index2]
            if num1 == num2 {
                if intersection.isEmpty || num1 != intersection.last {
                    intersection.append(num1)
                }
                index1 += 1
                index2 += 1
            } else if num1 < num2 {
                index1 += 1
            } else {
                index2 += 1
            }
        }
        return intersection
    }
}

复杂度剖析

• 时刻复杂度：$O(m\log m+n\log n)$，其间 $m$ 和 $n$ 别离是两个数组的长度。对两个数组排序的时刻复杂度别离是 $O(m\log m)$ 和 $O(n\log n)$，双指针寻觅交集元素的时刻复杂度是 $O(m+n)$，因而总时刻复杂度是 $O(m\log m+n\log n)$。

• 空间复杂度：$O(logm+logn)$，其间 $m$ 和 $n$ 别离是两个数组的长度。空间复杂度首要取决于排序运用的额定空间。