数据结构（一）数组实现一个简单的ArrayList
数据结构（二）链表实现LinkedList
数据结构（三）用两种方式简单实现栈
数据结构（四）栈和队列的简单应用
数据结构（五）用两种方式简单实现队列
数据结构（六）二分搜索树(Binary Search Tree)（上）
数据结构（六）二分搜索树(Binary Search Tree)（下）
数据结构（七）两种方式实现set
数据结构（八）两种方式实现map
数据结构（九）set解决LeetCode349号问题
今天我们来看一下map解决LeetCode上第350题。题目如下
给定两个数组，编写一个函数来计算它们的交集。
示例 1:
输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2,2]
示例 2:
输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [4,9]
说明：
输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。
我们可以不考虑输出结果的顺序。
下边我们用map解决一下，源码如下
import java.util.ArrayList;
import java.util.TreeMap;
public class Solution350 {
public int[] intersect(int[] nums1, int[] nums2) {
TreeMap<Integer, Integer> map = new TreeMap<>();
for(int num: nums1){
if(!map.containsKey(num))
map.put(num, 1);
else
map.put(num, map.get(num) + 1);
}
ArrayList<Integer> res = new ArrayList<>();
for(int num: nums2){
if(map.containsKey(num)){
res.add(num);
map.put(num, map.get(num) - 1);
if(map.get(num) == 0)
map.remove(num);
}
}
int[] ret = new int[res.size()];
for(int i = 0 ; i < res.size() ; i ++)
ret[i] = res.get(i);
return ret;
}
}
这里我们创建了一个TreeMap，我们把num作为key，这个元素出现的次数作为value，
- 首先我们把数组1的值存入到map中，这里我们判断了一下这个map中有没有这个key，如果有的话就把对应的value+1，
- 其次我们遍历数组2，如果包含这个key，那么就把这个元素存入到ArrayList中，并且对应的map里的value对应减一，如果这个num对应的value是0的话我们就把从map中删掉。
- 最后我们把数据存到数组里就可以了。
好了这里就是我们简单的解决方法，如果大家有更好的方法欢迎在下边评论。
更多精彩请关注公众号及时接收
更多精彩请关注公众号及时接收
公众号
