给定两个数组，编写一个函数来计算它们的交集。
说明：
输出结果中每个元素出现的次数，应与元素在两个数组中出现次数的最小值一致。
我们可以不考虑输出结果的顺序。
进阶：
如果给定的数组已经排好序呢？你将如何优化你的算法？
如果 nums1 的大小比 nums2 小很多，哪种方法更优？
如果 nums2 的元素存储在磁盘上，内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？
摘一个示例做个说明.
示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]
条件分析:
- 不考虑顺序 ->只要结果,不考虑顺序,可以考虑使用哈希表
- 排序好 -> 进阶的话可以采用双指针进行查找
- 数组长度差别很大 -> 可以先考虑处理短数组
- 其中一个数据量大,分次读取 -> 考虑分批处理数据
解决思路1:
- 根据分析1、3、4,存储较短数组到哈希表,key为数组内容,value为出现次数
先遍历短数组,存储内容和次数到哈希表,然后遍历长数组,判断是否存在该值,存在的话,则加入到返回数组中,并且使出现次数减1,
解决思路2:
1.根据分析2,采用i,j分别存储指针位置.按照大小比较数组内容.然后指针相应右移.直到其中一个数组遍历完成.
先对数组进行排序,然后while循环,如果其中一个数据较小,则该指针右移,如果相等则同时右移.直到其中一个完成.
解决思路3:
采用可变数组进行处理,循环短数组,如果长数组存在该值则加入返回数组并且长数组删除该值.直到循环结束.
解决思路4:
对数组排序,然后循环短数组,如果长数组包含该值,且返回数组不包含该值.则找出两个数组中该值的起始索引和最终索引.然后根据长度,循环添加到返回数组中.
代码实现-Swift版本:
思路1代码:
func intersect(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
/**
遍历较短数组,然后存储该值和出现次数,再遍历长数组,存在该值则存储到返回数组,并哈希存储该值减一,
时间16ms, 100% 内存13.7MB, 78.57%
时间复杂度 M+N,空间复杂度Min(M,N)
*/
var array: [Int] = []
var map: [Int: Int] = [:]
if nums1.count > nums2.count{
for item in nums2 {
if map[item] == nil {
map.updateValue(1, forKey: item)
}else{
map.updateValue(map[item]! + 1, forKey: item)
}
}
for item in nums1 {
if map[item] != nil && map[item]! > 0 {
array.append(item)
map.updateValue(map[item]! - 1, forKey: item)
}
}
}else{
for item in nums1 {
if map[item] == nil {
map.updateValue(1, forKey: item)
}else{
map.updateValue(map[item]! + 1, forKey: item)
}
}
for item in nums2 {
if map[item] != nil && map[item]! > 0 {
array.append(item)
map.updateValue(map[item]! - 1, forKey: item)
}
}
}
return array
}
两个数组的交集 哈希表 提交结果.jpg
思路2代码:
func intersect(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
/**
双指针方式
时间32ms, 58.67% 内存13.9MB, 35.2%
总时间复杂度 O(mlogm + n logn),排序时间是O(mlogm + n logn)遍历是O(M + N),空间复杂度Min(M,N)
*/
var array: [Int] = []
let array1 = nums1.sorted()
let array2 = nums2.sorted()
var i = 0
var j = 0
while i != nums1.count && j != nums2.count {
if array1[i] == array2[j] {
array.append(array1[i])
i += 1
j += 1
}else if array1[i] > array2[j]{
j += 1
}else{
i += 1
}
}
return array
}
两个数组的交集 双指针 提交结果.jpg
思路3代码:
func intersect(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
/**
常规办法,第一个数组存储结果,第二三个可变数组存储原始数据.然后进行查找,如果存在,则在查找数组中删除.之后继续遍历,直到没有为止.
*/
var array: [Int] = []
var array1: [Int] = nums1
var array2: [Int] = nums2
if nums1.count > nums2.count{
for item in array2 {
if array1.contains(item) {
array.append(item)
let index = array1.firstIndex(of: item)!
array1.remove(at: index)
}
}
}else{
for item in array1 {
if array2.contains(item) {
array.append(item)
let index = array2.firstIndex(of: item)!
array2.remove(at: index)
}
}
}
return array
}
思路4代码:
func intersect(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
/**
先排序,然后找相同元素的区间,直接根据区间个数进行添加,直到结束,常规办法
*/
var array: [Int] = []
let array1 = nums1.sorted()
let array2 = nums2.sorted()
if nums1.count > nums2.count {
for item in array2 {
if array1.contains(item) && !array.contains(item) {
let array1FirstIndex = array1.firstIndex(of: item)!
let array1LastIndex = array1.lastIndex(of: item)!
let array2FirstIndex = array2.firstIndex(of: item)!
let array2LastIndex = array2.lastIndex(of: item)!
let intervalArray1 = array1LastIndex - array1FirstIndex
let intervalArray2 = array2LastIndex - array2FirstIndex
array.append(item)
if intervalArray1 > intervalArray2 {
for _ in 0 ..< intervalArray2 {
array.append(item)
}
}else{
for _ in 0 ..< intervalArray1 {
array.append(item)
}
}
}
}
}else{
for item in array1 {
if array2.contains(item) && !array.contains(item) {
let array1FirstIndex = array1.firstIndex(of: item)!
let array1LastIndex = array1.lastIndex(of: item)!
let array2FirstIndex = array2.firstIndex(of: item)!
let array2LastIndex = array2.lastIndex(of: item)!
let intervalArray1 = array1LastIndex - array1FirstIndex
let intervalArray2 = array2LastIndex - array2FirstIndex
array.append(item)
if intervalArray1 > intervalArray2 {
for _ in 0 ..< intervalArray2 {
array.append(item)
}
}else{
for _ in 0 ..< intervalArray1 {
array.append(item)
}
}
}
}
}
return array
}
测试用例:
// 存在交集
let array1 = [1,2,3,4,4,4,5,6,7,8,9]
let array2 = [4,4,4,4,6,7,18,19,25,6757,89,23,97,46,67,34,54,889]
// 不存在交集
let array1 = [1,2,3,4,4,4,5,6,7,8,9]
let array2 = [18,19,25,6757,89,23,97,46,67,34,54,889]
考察要点:
- 数组
- 哈希表
- 双指针
- 排序
- 二分查找 在排序上采用二分查找,代码段上未手动实现
网友评论