初级算法-数组-两个数组的交集 II

2021-07-31 本文已影响0人 coenen

给定两个数组，编写一个函数来计算它们的交集。

说明：
输出结果中每个元素出现的次数，应与元素在两个数组中出现次数的最小值一致。
我们可以不考虑输出结果的顺序。
进阶：
如果给定的数组已经排好序呢？你将如何优化你的算法？
如果 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]

考察要点:

数组
哈希表
双指针
排序
二分查找 在排序上采用二分查找,代码段上未手动实现