关于leetcode:每日一练46两个数组的交集

title: 每日一练（46）：两个数组的交加

categories:[剑指 offer]

tags:[每日一练]

date: 2022/04/21

每日一练（46）：两个数组的交加

给定一个蕴含 [0, n] 中 n 个数的数组 nums，找出 [0, n] 这个范畴内没有呈现在数组中的那个数。

示例 1：

输出：nums = [3,0,1]

输入：2

解释：n = 3，因为有 3 个数字，所以所有的数字都在范畴 [0,3] 内。2 是失落的数字，因为它没有呈现在 nums 中。

示例 2：

输出：nums = [0,1]

输入：2

解释：n = 2，因为有 2 个数字，所以所有的数字都在范畴 [0,2] 内。2 是失落的数字，因为它没有呈现在 nums 中。

示例 3：

输出：nums = [9,6,4,2,3,5,7,0,1]

输入：8

解释：n = 9，因为有 9 个数字，所以所有的数字都在范畴 [0,9] 内。8 是失落的数字，因为它没有呈现在 nums 中。

示例 4：

输出：nums = [0]

输入：1

解释：n = 1，因为有 1 个数字，所以所有的数字都在范畴 [0,1] 内。1 是失落的数字，因为它没有呈现在 nums 中。

提醒：

n == nums.length

1 <= n <= 104

0 <= nums[i] <= n

nums 中的所有数字都 举世无双

起源：力扣（LeetCode）

链接：https://leetcode-cn.com/probl…

办法一：简略哈希

思路剖析

遍历 nums1 用 cnt 记录，cnt[i] 示意 i 这个数在 nums 中呈现过几次。

遍历 nums2，判断 cnt[i] 是否大于 0，大于阐明 nums1 中有这个数字，记得把 cnt[i] = 0，否则反复增加雷同的数字。

vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {int cnt[1001]{0};
    vector<int> res;
    for (auto i : nums1) {cnt[i]++;
    }
    for (auto i : nums2) {if (cnt[i] > 0) {res.push_back(i);
            cnt[i] = 0;
        }
    }
    return res;
}

办法二：Set 法

思路剖析

首先定义一个 set 容器将 nums1 拷贝到外面而后遍历 nums2 数组查看 map 容器中是否有 nums2 中元素如果存在则将值保留下来

vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
    unordered_set<int> result;
    unordered_set<int> nums1_set(nums1.begin(), nums1.end());/* 因为输入的元素惟一不反复因而能够将 nums1 转化为 unordered_set 哈希表 */
    for (int i = 0; i < nums2.size(); i++) {if (nums1_set.find(nums2[i]) != nums1_set.end()) { /* 判断 nums1_set 中是否有 nums2 的元素，若有将此值插入到 result */
            result.insert(nums2[i]);
        }
    }
    return vector<int> (result.begin(), result.end());
}