数据结构(一)数组实现一个简单的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中删掉。
- 最后我们把数据存到数组里就可以了。
好了这里就是我们简单的解决方法,如果大家有更好的方法欢迎在下边评论。
更多精彩请关注公众号及时接收
更多精彩请关注公众号及时接收
网友评论