题目
给定两个数组,编写一个函数来计算它们的交集。
示例 1:
输入:nums1 = [1,2,2,1], nums2 = [2,2] 输出:[2]
示例 2:
输入:nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出:[9,4]
解题
方法一:集合
python解法
用集合的办法,直接去求交集,(因为输出的每个元素是唯一的)
class Solution: def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]: return list(set(nums1)&set(nums2))
c++解法
class Solution { public: vector<int> intersection(vector<int>& nums1, vector<int>& nums2) { unordered_set<int> result_set; unordered_set<int> nums_set(nums1.begin(),nums1.end()); for(int num:nums2){ if(nums_set.find(num)!=nums_set.end()){ result_set.insert(num); } } return vector<int>(result_set.begin(),result_set.end()); } };
java解法
class Solution { public int[] intersection(int[] nums1, int[] nums2) { Set<Integer> set=new HashSet<>(); Set<Integer> res=new HashSet<>(); for(int val:nums1){ set.add(val); } for(int val:nums2){ if(set.contains(val)){ res.add(val); } } int[] ans=new int[res.size()]; int i=0; for(int val:res){ ans[i]=val; i++; } return ans; } }
方法二:哈希map
c++解法
class Solution { public: vector<int> intersection(vector<int>& nums1, vector<int>& nums2) { unordered_map<int,int> map; vector<int> res; for(int num:nums1) map[num]++;//统计nums1中每个数出现次数,记录哈希map中 for(int num:nums2){ if(map[num]>0){ res.push_back(num); map[num]=0;//避免重复加入 } } return res; } };
java解法
class Solution { public int[] intersection(int[] nums1, int[] nums2) { List<Integer> list=new ArrayList<>(); Map<Integer,Integer> mp=new HashMap<>(); for(int i=0;i<nums1.length;i++){ mp.put(nums1[i],mp.getOrDefault(nums1[i],0)+1); } for(int i=0;i<nums2.length;i++){ if(mp.getOrDefault(nums2[i],0)>0){ list.add(nums2[i]); mp.put(nums2[i],0); } } //List<Integer>转int[] int[] res=new int[list.size()]; int i=0; for(Integer integer:list){ res[i]=integer; i++; } return res; } }