leetcode 349. Intersection of Two Arrays 两个数组的交集

傷城~ 2022-06-07 01:16 130阅读 0赞

Given two arrays, write a function to compute their intersection.

Example:  
Given nums1 = \[1, 2, 2, 1\], nums2 = \[2, 2\], return \[2\].

Note:  
Each element in the result must be unique.  
The result can be in any order.

这道题考察的是两个数组的交集，可以使用HashSet和HashMap来做。

代码如下：

import java.util.ArrayList;
    import java.util.HashMap;
    import java.util.HashSet;
    import java.util.List;
    import java.util.Map;
    import java.util.Set;
    
    
    /*
     * 使用HashMap要比使用Set高明多了
     * */
    class Solution 
    {
          public int[] intersection(int[] nums1, int[] nums2) 
          {
                if(nums1==null || nums1.length<=0 || nums2==null || nums2.length<=0)
                    return new int[0];
    
                List<Integer> res=new ArrayList<Integer>();
                Map<Integer, Boolean> map1=new HashMap<Integer, Boolean>();
                for(int i=0;i<nums1.length;i++)
                    map1.put(nums1[i], true);
    
                for(int i=0;i<nums2.length;i++)
                {
                    if(map1.containsKey(nums2[i]))
                    {
                        res.add(nums2[i]);
                        map1.remove(nums2[i]);
                    }
                }
                int[] res1=new int[res.size()];
                for(int i=0;i<res1.length;i++)
                    res1[i]=res.get(i);
                return res1;
          }
    
    
        public int[] intersectionByHashSet(int[] nums1, int[] nums2) 
        {
            if(nums1==null || nums1.length<=0 || nums2==null || nums2.length<=0)
                return new int[0];
            Set<Integer> s=new HashSet<>();
            for(int i=0;i<nums1.length;i++)
                s.add(nums1[i]);
    
            Set<Integer> ss=new HashSet<>();
            for(int i=0;i<nums2.length;i++)
                ss.add(nums2[i]);
    
            s.retainAll(ss);
            List<Integer> res=new ArrayList<Integer>(s);
            int[] res1=new int[res.size()];
            for(int i=0;i<res1.length;i++)
                res1[i]=res.get(i);
            return res1;
        }
    }

下面是C++的做法，使用set即可

注意这里的set在做查询的时候，查询结束之后并删除相关元素

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    
    using namespace std;
    
    
    class Solution 
    {
    public:
        vector<int> intersection(vector<int>& nums1, vector<int>& nums2) 
        {
            set<int> ss;
            for (int i : nums1)
                ss.insert(i);
    
            vector<int> res;
            for (int i : nums2)
            {
                if (ss.find(i) != ss.end())
                {
                    res.push_back(i);
                    ss.erase(i);
                }
            }
    
            return res;
        }
    };