LeetCode 刷题 Swift 两个数组的交集
题目
给定两个数组 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 } }
复杂度分析
方法二:排序 + 双指针
思路及解法
如果两个数组是有序的,则可以使用双指针的方法得到两个数组的交集。
首先对两个数组进行排序,然后使用两个指针遍历两个数组。可以预见的是加入答案的数组的元素一定是递增的,为了保证加入元素的唯一性,我们需要额外记录变量 pre\textit{pre}pre 表示上一次加入答案数组的元素。
初始时,两个指针分别指向两个数组的头部。每次比较两个指针指向的两个数组中的数字,如果两个数字不相等,则将指向较小数字的指针右移一位,如果两个数字相等,且该数字不等于 pre\textit{pre}pre ,将该数字添加到答案并更新 pre\textit{pre}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 } }
复杂度分析
以上就是LeetCode 刷题 Swift 两个数组的交集的详细内容,更多关于Swift 两个数组交集的资料请关注编程宝库其它相关文章!
题目给定一个 正整数 num,编写一个函数,如果 num 是一个完全平方数,则返回 true,否则返回 false。进阶:不要 使用任何内置的库函数,如sqrt。示例 1:输 ...