这道题的意思很明确,就是让寻找两个数组中的共同元素,并去重,由此可以联想到哈希表的特性,注意到题目给的数据范围,在1000以内,所以本题可以使用 STL 的库函数,也可以使用数组进行模拟。
本题要求去重的交集,因此选用unordered_set。相比于set(红黑树实现,O(log n)查找),unordered_set(哈希表实现,平均O(1)查找)在效率上更优。
class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {// 使用unordered_set存储nums1的元素,自动去重unordered_set<int> st(nums1.begin(), nums1.end());// 用于存储结果的集合,保证结果中的元素唯一unordered_set<int> result;// 遍历nums2中的每个元素for(int i = 0; i < nums2.size(); i++) {// 检查当前元素是否存在于nums1中(即是否在st集合中)if(st.find(nums2[i]) != st.end()) {// 如果存在,则将该元素加入结果集合result.insert(nums2[i]);}}// 将结果集合转换为vector返回return vector<int>(result.begin(), result.end());}
};