【数据结构和算法】找出两数组的不同

其他系列文章导航

Java基础合集
数据结构与算法合集

设计模式合集

多线程合集

分布式合集

ES合集


文章目录

其他系列文章导航

文章目录

前言

一、题目描述

二、题解

2.1 哈希类算法题注意事项

2.2 方法一:哈希法

三、代码

3.1 方法一:哈希法

四、复杂度分析

4.1 方法一:哈希法


前言

这是力扣的 2215 题,难度为简单,解题方案有很多种,本文讲解我认为最奇妙的一种。


一、题目描述

给你两个下标从 0 开始的整数数组 nums1 和 nums2 ,请你返回一个长度为 2 的列表 answer ,其中:

  • answer[0] 是 nums1 中所有 不 存在于 nums2 中的 不同 整数组成的列表。
  • answer[1] 是 nums2 中所有 不 存在于 nums1 中的 不同 整数组成的列表。

注意:列表中的整数可以按 任意 顺序返回。

示例 1:

输入:nums1 = [1,2,3], nums2 = [2,4,6]
输出:[[1,3],[4,6]]
解释:
对于 nums1 ,nums1[1] = 2 出现在 nums2 中下标 0 处,然而 nums1[0] = 1 和 nums1[2] = 3 没有出现在 nums2 中。因此,answer[0] = [1,3]。
对于 nums2 ,nums2[0] = 2 出现在 nums1 中下标 1 处,然而 nums2[1] = 4 和 nums2[2] = 6 没有出现在 nums2 中。因此,answer[1] = [4,6]。

示例 2:

输入:nums1 = [1,2,3,3], nums2 = [1,1,2,2]
输出:[[3],[]]
解释:
对于 nums1 ,nums1[2] 和 nums1[3] 没有出现在 nums2 中。由于 nums1[2] == nums1[3] ,二者的值只需要在 answer[0] 中出现一次,故 answer[0] = [3]。
nums2 中的每个整数都在 nums1 中出现,因此,answer[1] = [] 。 

提示:

  • 1 <= nums1.length, nums2.length <= 1000
  • -1000 <= nums1[i], nums2[i] <= 1000

二、题解

2.1 哈希类算法题注意事项

解决哈希类的算法题需要注意以下几点:

  1. 理解哈希表的基本原理:哈希表是一种数据结构,它使用哈希函数将键映射到数组中的位置。理解哈希表如何工作是解决这类问题的关键。
  2. 选择合适的哈希函数:一个好的哈希函数能够将键均匀地分布到哈希表中,以减少冲突。你需要选择或设计一个能够满足题目要求的哈希函数。
  3. 处理冲突:即使有好的哈希函数,也可能会有冲突(即两个不同的键映射到同一个位置)。你需要决定如何处理这些冲突,例如使用链表、开放地址法等。
  4. 考虑哈希表的负载因子:负载因子是哈希表中元素的数量与哈希表大小的比值。当负载因子过高时,哈希表的性能会下降。因此,你可能需要动态调整哈希表的大小以保持合适的负载因子。
  5. 优化空间和时间效率:在解决这类问题时,你需要权衡空间和时间效率。一个空间效率高的解决方案可能不那么高效,反之亦然。你需要找到一个合适的平衡点。
  6. 测试和验证:在提交解决方案之前,一定要进行彻底的测试和验证。确保你的解决方案在各种情况下都能正常工作。
  7. 阅读和理解题目要求:仔细阅读题目,确保你完全理解了题目的要求。如果有任何疑问,应该向老师或教练询问,以确保没有误解。
  8. 使用适当的数据结构:在许多情况下,使用哈希表并不是唯一的解决方案。其他数据结构(如数组、树或图)可能更适合解决特定的问题。选择最适合的数据结构可以提高解决问题的效率。
  9. 注意算法的复杂度:了解算法的时间复杂度和空间复杂度对于选择合适的算法非常重要。对于大规模数据,应选择复杂度较低的算法以提高效率。
  10. 多做练习:解决哈希类的算法题需要大量的练习和经验积累。通过参与在线编程挑战、参加算法竞赛等方式,可以提高解决这类问题的能力。

2.2 方法一:哈希法

思路与算法:

为了较快地判断一个数组的某个元素是否在另一个数组中存在,我们可以用哈希集合来存储数组的元素,并进行判断。具体而言,我们用哈希集合 set1 与 set2 存储数组 nums1 与 nums2 中所有不同的元素。

我们用长度为 2 的嵌套列表 res 来保存两数组中不存在于另一数组中的元素。

新建五个空间:

  • res
  • list1
  • list2
  • set1
  • set2

我们首先遍历哈希集合 num1的每个元素存入 list1 中,然后遍历哈希集合 num2 的每个元素存入 list2 中。

接着遍历 num1 和 num2 。

  • 如果 set2 不存在 num1 的元素,同时 list2 不存在这个元素,则加入到 list2 中。
  • 如果 set1 不存在 num2 的元素,同时 list1 不存在这个元素,则加入到 list1 中。

最后把 list1 和 list2 加入到 res 中。


三、代码

3.1 方法一:哈希法

Java版本:

class Solution {
    public List<List<Integer>> findDifference(int[] nums1, int[] nums2) {
        List<List<Integer>> res = new ArrayList<>();
        HashSet<Integer> set1 = new HashSet<>();
        HashSet<Integer> set2 = new HashSet<>();
        ArrayList<Integer> list1 = new ArrayList<>();
        ArrayList<Integer> list2 = new ArrayList<>();
        for (int i : nums1) {
            set1.add(i);
        }
        for (int i : nums2) {
            set2.add(i);
        }
        for (int i : nums1) {
            if (!set2.contains(i)&&!list2.contains(i)) list2.add(i);
        }
        for (int i : nums2) {
            if (!set1.contains(i)&&!list1.contains(i)) list1.add(i);
        }
        res.add(list2);
        res.add(list1);
        return res;
    }
}

C++版本:

class Solution {
public:
    std::vector<std::vector<int>> findDifference(std::vector<int>& nums1, std::vector<int>& nums2) {
        std::vector<std::vector<int>> res;
        std::unordered_set<int> set1(nums1.begin(), nums1.end());
        std::unordered_set<int> set2(nums2.begin(), nums2.end());
        std::vector<int> list1, list2;
        for (int i : nums1) {
            if (set2.find(i) == set2.end() && std::find(list2.begin(), list2.end(), i) == list2.end()) {
                list2.push_back(i);
            }
        }
        for (int i : nums2) {
            if (set1.find(i) == set1.end() && std::find(list1.begin(), list1.end(), i) == list1.end()) {
                list1.push_back(i);
            }
        }
        res.push_back(list2);
        res.push_back(list1);
        return res;
    }
};

Python版本:

class Solution:
    def findDifference(self, nums1, nums2):
        res = []
        set1 = set(nums1)
        set2 = set(nums2)
        list1 = [i for i in nums1 if i not in set2]
        list2 = [i for i in nums2 if i not in set1]
        res.append(list2)
        res.append(list1)
        return res

Go版本:

import "sort"

func findDifference(nums1 []int, nums2 []int) [][]int {
    res := make([][]int, 2)

    set1 := make(map[int]bool)
    set2 := make(map[int]bool)

    for _, num := range nums1 {
        set1[num] = true
    }
    for _, num := range nums2 {
        set2[num] = true
    }

    for _, num := range nums1 {
        if !set2[num] {
            res[1] = append(res[1], num)
            set2[num] = true
        }
    }
    sort.Ints(res[1])

    for _, num := range nums2 {
        if !set1[num] {
            res[0] = append(res[0], num)
            set1[num] = true
        }
    }
    sort.Ints(res[0])

    return res
}

四、复杂度分析

4.1 方法一:哈希法

  • 时间复杂度:O(N)。
  • 空间复杂度:O(N)。