# LeetCode-ALg-350-IntersectionofTwoArraysII

## Algorithm-Easy

Posted by Jae on December 7, 2018

### 1、题目

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

Example 1:

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]


Example 2:

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [4,9]


Note:

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


### 2、思路

• 首先想到定义一个字典，将一个长度较短的数组中的元素作为字典的key，出现的次数作为value存储到字典中，然后遍历另一个数组，如果元素在字典中，且字典对应的value大于0，就将该元素存放到结果集中，同时将该值对应的value值减小1。

### 3、实现(Java)

public int[] intersect(int[] nums1, int[] nums2) {
if (nums1.length == 0 || nums2.length == 0)
{
return new int[0];
}
HashMap<Integer, Integer> map = new HashMap<>();
int k = 0;

if (nums1.length >= nums2.length)
{
for (int elem : nums2)
{
// 这里的containsKey() get() put()操作比较耗时
int count = map.containsKey(elem) ? map.get(elem) : 0;
map.put(elem, count + 1);
}

int[] result = new int[nums1.length];
for (int i : nums1)
{
if (map.containsKey(i) && map.get(i) > 0)
{
result[k] = i;
map.put(i, map.get(i) - 1);
k++;
}
}
return Arrays.copyOfRange(result, 0, k);
}else
{
return intersect(nums2, nums1);
}
}