LeetCode 349 Intersection of Two Arrays

LeetCode 349 Intersection of Two Arrays

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，然后遍历另一个数组判断是否相同，相同的话放入hashSet的结果集中。所以需要两个hashSet。

Python代码：

def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
    return list(set(nums1) & set(nums2))

Java代码：

public int[] intersection(int[] nums1, int[] nums2) {
	//swap and make sure length of nums1 is smaller
	if(nums1.length>nums2.length){
		int[] tmp = nums1;
		nums1 = nums2;
		nums2 = tmp;
	}
	
	Set<Integer> hash=new HashSet();
	Set<Integer> result=new HashSet();
	for(int i=0;i<nums1.length;i++)
		hash.add(nums1[i]);
	
	for(int i=0; i<nums2.length;i++){
		if(hash.contains(nums2[i]))
			result.add(nums2[i]);
	}
	int[] r=new int[result.size()];
	int k=0;
	for(int i : result)
		r[k++]=i;
	return r;       
}

算法分析：

m和n为数组长度m>n，时间复杂度为O(m)，空间复杂度O(n)。