KK's blog

每天积累多一些

0%

LeetCode 350 Intersection of Two Arrays II

Posted on Edited on Disqus:

LeetCode 350 Intersection of Two Arrays II

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

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

Note:

  • Each element in the result should appear as many times as it shows in both arrays.
  • The result can be in any order.

Follow up:

  • What if the given array is already sorted? How would you optimize your algorithm?
  • What if nums1‘s size is small compared to nums2‘s size? Which algorithm is better?
  • What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

题目大意：

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

注意：
结果中的每个元素的出现次数应与其在两个数组中同时出现的次数一样多。 结果可以采用任意顺序。

进一步思考：
如果数组已经排好序，怎样优化你的算法？
如果nums1的长度＜nums2的长度？哪一种算法更好？
如果nums2的元素存储在磁盘上，并且内存大小有限，不足以将其一次性的加载到内存中。此时应当怎样做？

解题思路：

类似于L349，但由于可允许重复，所以改hashSet成hashMap记录频数。具体而言，将较小的数组的所有元素放入hashMap且统计频数，
然后遍历另一个数组判断是否相同，相同的话放入ArrayList的结果集中且频数减一。

Python代码：

1
2
3
4
5
6
7
8
def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
	num_to_count = collections.Counter(nums1)
	res = []
	for n in nums2:
		if n in num_to_count and num_to_count[n] > 0:
			num_to_count[n] -= 1
			res.append(n)
	return res

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public int[] intersect(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;
	}
	
	Map<Integer, Integer> map=new HashMap<Integer, Integer>();
	List<Integer> result=new ArrayList();
	for(int i=0;i<nums1.length;i++){
		if(map.containsKey(nums1[i]))
			map.put(nums1[i], map.get(nums1[i])+1);
		else
			map.put(nums1[i],1);
	}
	
	for(int i=0; i<nums2.length;i++){
		if(map.containsKey(nums2[i]) && map.get(nums2[i])>0){
			result.add(nums2[i]);
			map.put(nums2[i], map.get(nums2[i])-1);
		}
	}
	return result.stream().mapToInt(i->i).toArray();      
}

算法分析：

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

算法II解题思路：

另一个解题思路是，先对它们排序，然后类似于mergeSort算法维持两个指针分别在两个数组搜索相同元素。

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int[] intersect(int[] nums1, int[] nums2) {
	List<Integer> result=new ArrayList();
	Arrays.sort(nums1);
	Arrays.sort(nums2);
	int i=0, j=0;
	while(i<nums1.length && j<nums2.length){
		if(nums1[i]==nums2[j]){
			result.add(nums1[i]);
			i++;
			j++;
		}
		else if(nums1[i]<nums2[j])
			i++;
		else j++;
	}
	return result.stream().mapToInt(k->k).toArray();
}

算法分析：

m和n为数组长度m>n，时间复杂度为O(mlogm)，空间复杂度O(1)。此算法空间较优，但时间稍逊。

  1. 如果数组已经排好序，怎样优化你的算法？
    用第二个算法，时间复杂度为O(m),但空间复杂度可以优化为O(1)
  2. 如果nums1的长度＜nums2的长度？哪一种算法更好？
    方法一更优，因为nums1空间用的比较少情况下
  3. 如果nums2的元素存储在磁盘上，并且内存大小有限，不足以将其一次性的加载到内存中。此时应当怎样做？
    也应该用方法一，因为它不需要把nums2数组一次性加载到内存中。假设内存大小为L，每次L大小的内存可解决
    部分问题，时间复杂度为O(m),然后有n/L次，最后结果为O(mn)，表示空间有限时候，hashSet的方法不比先排序快。

第三种方法是一个数组排序，另一个可以不排序。不排序数组的每个元素在排序数组中用二分法查找。

Free mock interview