2215-找出两数组的不同

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:29 2023-09-13 16:06:29 Updated    

给你两个下标从 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

方法一：哈希集合

思路与算法

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

我们用长度为 2 的嵌套列表 res 来保存两数组中不存在于另一数组中的元素。我们首先遍历哈希集合 set}_1 的每个元素，判断其是否位于 set}_2 中，如果不在，则我们将它加入 res}[0] 中；随后我们同样地遍历哈希集合 set}_2 的每个元素，判断其是否位于 set}_1 中，如果不在，则加入 res}[1] 中。这样，我们就得到了两数组中各自的不同元素。

与此同时，由于哈希集合 set}_1 与 set}_2 中不存在重复元素，因此 res}[0] 与 res}[1] 也一定不存在重复元素。最终我们返回 res 作为答案即可。

代码

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<vector<int>> findDifference(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> set1, set2;   // nums1 与 nums2 所有元素的哈希集合
        for (int num: nums1) {
            set1.insert(num);
        }
        for (int num: nums2) {
            set2.insert(num);
        }
        vector<vector<int>> res(2);
        for (int num: set1) {
            if (!set2.count(num)) {
                res[0].push_back(num);
            }
        }
        for (int num: set2) {
            if (!set1.count(num)) {
                res[1].push_back(num);
            }
        }
        return res;
    }
};
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def findDifference(self, nums1: List[int], nums2: List[int]) -> List[List[int]]:
        set1 = set(nums1)   # nums1 所有元素的哈希集合
        set2 = set(nums2)   # nums2 所有元素的哈希集合
        res = [[], []]
        for num in set1:
            if num not in set2:
                res[0].append(num)
        for num in set2:
            if num not in set1:
                res[1].append(num)
        return res

复杂度分析

  • 时间复杂度：O(n_1 + n_2)，其中 n_1 与 n_2 分别为数组 nums}_1 和 nums}_2 的长度。维护两数组元素对应哈希集合与遍历计算答案的时间复杂度均为 O(n_1 + n_2)。

  • 空间复杂度：O(n_1 + n_2)，即为两数组元素对应哈希集合的空间开销。

 Comments
On this page
2215-找出两数组的不同