package com.lt.datastructure.Set;

import java.util.ArrayList;

import java.util.LinkedHashSet;

import java.util.LinkedList;

import java.util.TreeSet;

/*

 * LeetCode409 给定两个数组，编写其中一个函数来计算他们的交集

 * 说明:

        输出结果中的每个元素一定是唯一的。

        我们可以不考虑输出结果的顺序。

    思路：

      遍历数组1，存入集合TreeSet

      遍历数组2，如果集合中含有数组2的元素，存入list，同时在集合中删除此元素(因为数组无法去重)

      新建数组3， 将动态数组list元素存入数组3并打印     

 */

class Solution {

    public int[] intersection(int[] nums1, int[] nums2)

    {

          ArrayList<Integer> list = new ArrayList<>();

          TreeSet<Integer> set = new TreeSet<>();

          for(int num : nums1){

              set.add(num);

          }

          for(int num : nums2){

              if(set.contains(num)){

                  list.add(num);

                  set.remove(num);

              }

          }

          int[] res = new int[list.size()];

          for(int i =0 ; i<list.size() ; i++){

              res[i] = list.get(i);

          }

          return res;

    }

}

package com.lt.datastructure.Set;

import java.util.ArrayList;

import java.util.TreeMap;

/**

 * leetCode350

定两个数组，编写一个函数来计算它们的交集。

示例 1:

输入: nums1 = [1,2,2,1], nums2 = [2,2]

输出: [2,2]

说明：

    输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。

    我们可以不考虑输出结果的顺序。

思路：  用映射实现，k存值，v存次数

             遍历数组1，如果map中不含有被遍历的元素，将其存入map, 设置次数即value为1

                如果map中含有被遍历的元素，   将其存入map, 次数为原来的基础上+1

       遍历数组2，如果map中包含被遍历的元素，将其存入list,同时次数-1

                    当次数为0的时候，将其从map中移除

             新建数组res，将动态数组list的值存入res,返回res               

 */

class Solution3 {

    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> list = new ArrayList<>();

        for(int num : nums2){

            if(map.containsKey(num)){

                list.add(num);

                map.put(num , map.get(num)-1);

                if(map.get(num)==0){

                    map.remove(num);

                }

            }

        }

        int[] res = new int[list.size()];

        for(int i =0; i<list.size(); i++){

            res[i] = list.get(i);

        }

        return res;

    }

}