美文网首页
数据结构(十)map解决LeetCode350

数据结构(十)map解决LeetCode350

作者: Merlin_720 | 来源:发表于2019-09-16 08:24 被阅读0次

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

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

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

    公众号

    相关文章

      网友评论

          本文标题:数据结构(十)map解决LeetCode350

          本文链接:https://www.haomeiwen.com/subject/sdsoectx.html