LeetCode?刷題?Swift?兩個(gè)數(shù)組的交集
題目
給定兩個(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]
解釋?zhuān)?/strong> [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
}
}
復(fù)雜度分析
以上就是LeetCode 刷題 Swift 兩個(gè)數(shù)組的交集的詳細(xì)內(nèi)容，更多關(guān)于Swift 兩個(gè)數(shù)組交集的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
很多朋友糾結(jié)為什么為什么switch里的case沒(méi)有break不行呢？break這么重要么，今天小編就給大家普及下這方便的知識(shí)，感興趣的朋友一起看看吧2021-06-06
Swift?Error重構(gòu)的基礎(chǔ)示例詳解
這篇文章主要為大家介紹了Swift?Error基礎(chǔ)錯(cuò)誤處理的方法詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-11-11
Swift 4是蘋(píng)果計(jì)劃于2017年秋季推出的最新版本，其主要重點(diǎn)是提供與Swift 3代碼的源兼容性，并努力實(shí)現(xiàn)ABI穩(wěn)定性。下面這篇文章主要給大家介紹了關(guān)于swift 4.0中private所發(fā)生的一些變化，需要的朋友可以參考下。2017-12-12
這篇文章主要介紹了Swift教程之集合類(lèi)型詳解,Swift 提供兩種集合類(lèi)型來(lái)存儲(chǔ)集合,數(shù)組和字典,本文詳細(xì)講解了數(shù)組的創(chuàng)建、讀取和修改數(shù)組、遍歷數(shù)組以及集合的操作等內(nèi)容,需要的朋友可以參考下2015-01-01
在一個(gè)項(xiàng)目中同時(shí)使用Swift和Objective-C代碼混合編程的方法
這篇文章主要介紹了在一個(gè)項(xiàng)目中同時(shí)使用Swift和Objective-C代碼的方法,在一個(gè)工程中同時(shí)使用Swift和Objective-C混合語(yǔ)言編程的方法,需要的朋友可以參考下2014-07-07
SwiftUI?引導(dǎo)頁(yè)界面實(shí)現(xiàn)示例
這篇文章主要為大家介紹了SwiftUI?引導(dǎo)頁(yè)界面實(shí)現(xiàn)示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-09-09
本地推送通知UserNotifications在Swift中的實(shí)現(xiàn)方式
這篇文章主要介紹了本地推送通知UserNotifications在Swift中的實(shí)現(xiàn)方式，想了解消息推送的同學(xué)，一定要看一下2021-04-04
Swift實(shí)現(xiàn)“或”操作符的3種方法示例
這篇文章主要給大家介紹了關(guān)于Swift實(shí)現(xiàn)“或”操作符的3種方法，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2019-03-03
Swift使用Cocoa中的數(shù)據(jù)類(lèi)型教程
這篇文章主要介紹了Swift使用Cocoa中的數(shù)據(jù)類(lèi)型教程,Swift 會(huì)自動(dòng)將一些 Objective-C 類(lèi)型轉(zhuǎn)換為 Swift 類(lèi)型，以及將 Swift 類(lèi)型轉(zhuǎn)換為 Objective-C 類(lèi)型,需要的朋友可以參考下2014-07-07
這篇文章主要介紹了Swift教程之繼承詳解,一個(gè)類(lèi)可以從另外一個(gè)類(lèi)中繼承方法,屬性或者其它的一些特性,當(dāng)一個(gè)類(lèi)繼承于另外一個(gè)類(lèi)時(shí),這個(gè)繼承的類(lèi)叫子類(lèi),被繼承的類(lèi)叫父類(lèi),需要的朋友可以參考下2015-01-01