title: 每日一練（46）：兩個(gè)數(shù)組的交集
categories:[劍指offer]
tags:[每日一練]
date: 2022/04/21
每日一練（46）：兩個(gè)數(shù)組的交集
給定一個(gè)包含 [0, n] 中 n 個(gè)數(shù)的數(shù)組 nums 禀挫，找出 [0, n] 這個(gè)范圍內(nèi)沒(méi)有出現(xiàn)在數(shù)組中的那個(gè)數(shù)碳褒。
示例 1：
輸入：nums = [3,0,1]
輸出：2
解釋：n = 3胸哥，因?yàn)橛?3 個(gè)數(shù)字叫榕，所以所有的數(shù)字都在范圍 [0,3] 內(nèi)器净。2 是丟失的數(shù)字糕殉，因?yàn)樗鼪](méi)有出現(xiàn)在 nums 中颈将。
示例 2：
輸入：nums = [0,1]
輸出：2
解釋：n = 2昌阿，因?yàn)橛?2 個(gè)數(shù)字饥脑，所以所有的數(shù)字都在范圍 [0,2] 內(nèi)。2 是丟失的數(shù)字懦冰，因?yàn)樗鼪](méi)有出現(xiàn)在 nums 中灶轰。
示例 3：
輸入：nums = [9,6,4,2,3,5,7,0,1]
輸出：8
解釋：n = 9，因?yàn)橛?9 個(gè)數(shù)字刷钢，所以所有的數(shù)字都在范圍 [0,9] 內(nèi)笋颤。8 是丟失的數(shù)字，因?yàn)樗鼪](méi)有出現(xiàn)在 nums 中内地。
示例 4：
輸入：nums = [0]
輸出：1
解釋：n = 1伴澄，因?yàn)橛?1 個(gè)數(shù)字，所以所有的數(shù)字都在范圍 [0,1] 內(nèi)阱缓。1 是丟失的數(shù)字非凌，因?yàn)樗鼪](méi)有出現(xiàn)在 nums 中。
提示：
n == nums.length
1 <= n <= 104
0 <= nums[i] <= n
nums 中的所有數(shù)字都 獨(dú)一無(wú)二
來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/missing-number
方法一：簡(jiǎn)單哈希
思路分析
遍歷 nums1 用 cnt 記錄荆针，cnt[i] 表示 i 這個(gè)數(shù)在 nums 中出現(xiàn)過(guò)幾次敞嗡。
遍歷 nums2颁糟，判斷 cnt[i] 是否大于 0，大于說(shuō)明 nums1 中有這個(gè)數(shù)字喉悴，記得把 cnt[i] = 0棱貌，否則重復(fù)添加相同的數(shù)字。
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法
思路分析
首先定義一個(gè)set容器將nums1拷貝到里面然后遍歷nums2數(shù)組查看map容器中是否有nums2中元素如果存在則將值保存下來(lái)
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> result;
unordered_set<int> nums1_set(nums1.begin(), nums1.end());/* 由于輸出的元素唯一不重復(fù)因此可以將nums1轉(zhuǎn)化為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());
}
