数据结构（十）map解决LeetCode350

数据结构（一）数组实现一个简单的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中删掉。
• 最后我们把数据存到数组里就可以了。

好了这里就是我们简单的解决方法，如果大家有更好的方法欢迎在下边评论。
更多精彩请关注公众号及时接收

更多精彩请关注公众号及时接收