两个数组的交集

Posted on Edited on In Word count in article: 1.1k Reading time ≈ 1 mins.
两个数组的交集

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

1
2
input：nums1 = [1,2,2,1], nums2 = [2,2]
res = [2,2]

输出结果中每个元素出现的次数，应与元素在两个数组中出现次数的最小值一致。
我们可以不考虑输出结果的顺序。

如果给定的数组已经排好序呢？你将如何优化你的算法？ 双指针
如果 nums1 的大小比 nums2 小很多，哪种方法更优？ map哈希
如果 nums2 的元素存储在磁盘上，内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？ 归并排序

map哈希

优化：比较两个数组的大小，选择小的那个数组做map哈希

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func intersect(nums1 []int, nums2 []int) []int {
    resMap := make(map[int]int, len(nums1))
    for _, v := range nums1 {
        if _, ok := resMap[v]; ok {
            resMap[v] += 1
        } else {
            resMap[v] = 1
        }
    }
    res := make([]int, 0, len(nums2))
    for _, v := range nums2 {
        if _, ok := resMap[v]; ok && resMap[v] >= 1 {
            res = append(res, v)
            resMap[v] -= 1
        }
    }
    return res
}

双指针

优化：如果已经排好序，则减少排序次数

不能用if else, if else是顺序执行，前面++后，最后一层判断会超出slice边界

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func intersect(nums1 []int, nums2 []int) []int {
    sort.Ints(nums1)
    sort.Ints(nums2)
    i, j := 0, 0
    var res []int
    for i < len(nums1) && j < len(nums2) {
        switch {
        case nums1[i] < nums2[j]:
            i++
        case nums1[i] > nums2[j]:
            j++
        case nums1[i] == nums2[j]:
            res = append(res, nums1[i])
            i++
            j++
        }
    }
    return res
}

归并排序优化三

可以将分割后的子数组写到单个文件中，归并时将小文件合并为更大的文件。当两个数组均排序完成生成两个大文件后，即可使用双指针遍历两个文件，如此可以使空间复杂度最低

也就是上面双指针，归并排序的思想