leetcode 349. 两个数组的交集

骑猪看日落 2022-12-13 10:00 184阅读 0赞

题目链接：[349. 两个数组的交集][349.]

给定两个数组，编写一个函数来计算它们的交集。

示例 1：

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

示例 2：

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
    输出：[9,4]

说明：

输出结果中的每个元素一定是唯一的。
    我们可以不考虑输出结果的顺序。

**思路1**

第一个`vector`转为`set`，然后遍历第二个`vector`，若第二个`vector`元素在`set`中存在，则把该元素存下来。最后因为题目输出要求元素唯一，故需要对`vector`去重出结果。[vector去重可以戳这里][vector]。

关于set，C++ 给提供了如下三种可用的数据结构

std::set
    std::multiset
    std::unordered_set

`std::set`和`std::multiset`底层实现都是红黑树，`std::unordered_set`的底层实现是哈希表， 使用`unordered_set` 读写效率是最高的，我们并不需要对数据进行排序，而且还不要让数据重复，所以选择`unordered_set`。

**AC代码**

class Solution {
    public:
        vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
    
            vector<int> res;
            unordered_set<int> st1(nums1.begin(), nums1.end());
            for(auto num : nums2)
            {
                if(st1.find(num) != std::end(st1) )
                {
                    res.push_back(num);
                }
            }
    
            unordered_set<int>s(res.begin(), res.end());
            res.assign(s.begin(), s.end());
    
            return res;
    
    
        }
    };

**思路2**

代码Rust版本还没写完，C++版本我先copy过来：

class Solution {
    public:
        vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
            vector<int> ans;
            // 创建一个哈希表
            unordered_map<int, int> m;
    
            // 在哈希表中存储数组nums1
            for(auto num : nums1)
                m[num]++;
    
            // 在数组nums2中查找
            for(auto num : nums2)
            {
                // 在哈希表（nums1）中存在 且 不在ans中
                if(m.count(num) != 0 && find(ans.begin(), ans.end(), num) == ans.end())
                    ans.push_back(num);
            }
            return ans;
        }
    };
    
    //链接：https://leetcode-cn.com/problems/intersection-of-two-arrays/solution/349-liang-ge-shu-zu-de-jiao-ji-by-sunny_smile/

Rust版本，待续。。。

use std::collections::HashMap;
    
    fn main() {
            let mut nums1:Vec<i32> = Vec::new();
            let mut nums2:Vec<i32> = Vec::new();
            let mut hmap = HashMap::new();
            
            for i in 0..10
            {
                nums1.push(2*i);
                nums2.push(i);
                
            }
            for (pos, ele) in nums1.iter().enumerate()
            {
                //println!("pos is: {:?}, and ele is {:?}", pos, ele);
                hmap.insert(pos, ele);
            }
            
            for (pos, ele) in nums2.iter().enumerate()
            {
                println!("pos is: {:?}, and ele is {:?}", pos, ele);
                
            }
    }

[349.]: https://leetcode-cn.com/problems/intersection-of-two-arrays
[vector]: https://blog.csdn.net/xiangxianghehe/article/details/90637998