LeetCode?刷題?Swift?兩個(gè)數(shù)組的交集

更新時(shí)間：2022年09月21日 14:54:36 作者：晨曦_iOS

這篇文章主要為大家介紹了LeetCode?刷題?Swift?兩個(gè)數(shù)組的交集示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

題目

給定兩個(gè)數(shù)組 nums1 和 nums2，返回它們的交集。輸出結(jié)果中的每個(gè)元素一定是唯一的。我們可以不考慮輸出結(jié)果的順序。

示例 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] 也是可通過(guò)的

方法一：兩個(gè)集合

思路及解法

計(jì)算兩個(gè)數(shù)組的交集，直觀的方法是遍歷數(shù)組 nums1，對(duì)于其中的每個(gè)元素，遍歷數(shù)組 nums2 判斷該元素是否在數(shù)組 nums2 中，如果存在，則將該元素添加到返回值。假設(shè)數(shù)組 nums1 和 nums2 的長(zhǎng)度分別是 m 和 n，則遍歷數(shù)組 nums1 需要 O(m) 的時(shí)間，判斷 nums1 中的每個(gè)元素是否在數(shù)組 nums2 中需要 O(n) 的時(shí)間，因此總時(shí)間復(fù)雜度是 O(mn)。

如果使用哈希集合存儲(chǔ)元素，則可以在 O(1)的時(shí)間內(nèi)判斷一個(gè)元素是否在集合中，從而降低時(shí)間復(fù)雜度。

首先使用兩個(gè)集合分別存儲(chǔ)兩個(gè)數(shù)組中的元素，然后遍歷較小的集合，判斷其中的每個(gè)元素是否在另一個(gè)集合中，如果元素也在另一個(gè)集合中，則將該元素添加到返回值。該方法的時(shí)間復(fù)雜度可以降低到 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
    }
}

復(fù)雜度分析

方法二：排序 + 雙指針

思路及解法

如果兩個(gè)數(shù)組是有序的，則可以使用雙指針的方法得到兩個(gè)數(shù)組的交集。

首先對(duì)兩個(gè)數(shù)組進(jìn)行排序，然后使用兩個(gè)指針遍歷兩個(gè)數(shù)組?？梢灶A(yù)見(jiàn)的是加入答案的數(shù)組的元素一定是遞增的，為了保證加入元素的唯一性，我們需要額外記錄變量 pre\textit{pre}pre 表示上一次加入答案數(shù)組的元素。

初始時(shí)，兩個(gè)指針?lè)謩e指向兩個(gè)數(shù)組的頭部。每次比較兩個(gè)指針指向的兩個(gè)數(shù)組中的數(shù)字，如果兩個(gè)數(shù)字不相等，則將指向較小數(shù)字的指針右移一位，如果兩個(gè)數(shù)字相等，且該數(shù)字不等于 pre\textit{pre}pre ，將該數(shù)字添加到答案并更新 pre\textit{pre}pre 變量，同時(shí)將兩個(gè)指針都右移一位。當(dāng)至少有一個(gè)指針超出數(shù)組范圍時(shí)，遍歷結(jié)束。

代碼

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
    }
}