CanTechLab

Can

Leetcode:349. 两个数组的交集

2024-06-27

Leetcode题目链接:349. 两个数组的交集

题目描述

给定两个数组 nums1 和 nums2 ,返回它们的交集。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序

题目示例

示例一

输入:nums1 = [1,2,2,1], nums2 = [2,2]
输出:[2]

示例二

输入:nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出:[9,4]
解释:[4,9] 也是可通过的

提示

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

解题思路

哈希表(set形式)

  • 使用unordered_set容器定义数组result,用于存放最终的数组交集

  • 使用unordered_set容器定义数组nums,并使用构造方法将nums1数组转换为set,用于后续num2查表

  • for循环遍历数组nums2,若能在nums集合中找到相应的元素,则该元素为两个集合共有的元素,即交集的组成部分,将其插入到result集合中(set自动去重)

  • 将结果数组result转换为vector形式返回

哈希表(数组形式)

  • 使用unordered_set容器定义数组result,用于存放最终的数组交集

  • 题设条件给出数据元素均小于等于一千,可定义稍大于一千的数组作为哈希表来解决此问题,即 int hash[1005] = {0}(此处将1005个元素均初始化为0,供后续使用)

  • for循环遍历数组nums1,将hash数组的对应位置元素置1,即该元素在nums1中出现

  • for循环遍历数组nums2,判断hash数组的对应位置元素是否为1,即nums2中该元素是否在nums1也曾出现过

    • 若出现则向result集合中插入该元素

    • 若无则不执行任何操作

  • 将结果数组result转换为vector形式返回

我的答案

//使用set容器
class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> result;
        unordered_set<int> nums(nums1.begin(), nums1.end());
        for(int num : nums2) {
            if(nums.find(num) != nums.end()) {
                result.insert(num);
            }
        }
        return vector<int>(result.begin(), result.end());
    }
};

//使用数组哈希表
class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> result;
        int hash[1005] = {0};
        for(int num : nums1) {
            hash[num] = 1;
        }
        for(int num : nums2) {
            if(hash[num] == 1) {
                result.insert(num);
            }
        }
        return vector<int>(result.begin(), result.end());
    }
};

提交结果