数据结构（九）set解决LeetCode349号问题

数据结构（一）数组实现一个简单的ArrayList
数据结构（二）链表实现LinkedList
数据结构（三）用两种方式简单实现栈
数据结构（四）栈和队列的简单应用
数据结构（五）用两种方式简单实现队列
数据结构（六）二分搜索树(Binary Search Tree)（上）
数据结构（六）二分搜索树(Binary Search Tree)（下）
数据结构（七）两种方式实现set
数据结构（八）两种方式实现map
数据结构（九）set解决LeetCode349号问题

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

示例 1:

输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2]
示例 2:

输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [9,4]

说明:

输出结果中的每个元素一定是唯一的。
我们可以不考虑输出结果的顺序。

这个是LeetCode上第349号问题，就是求两个数组里相同且不重复的数。一提到不重复我们就应该想到set，因为set存的都是不重复的数。好了话不多说我们先贴一下源码。

import java.util.ArrayList;
import java.util.TreeSet;

class Solution349 {
    public int[] intersection(int[] nums1, int[] nums2) {

        TreeSet<Integer> set = new TreeSet<>();
        for(int num: nums1)
            set.add(num);

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

解析

• 首先，我们创建了一个TreeSet，然后把num1的数存到里边，这时候num1的数就变成了没有重复元素的set了；
• 其次，我们也可以在创建一个TreeSet，把num2的数存到这个TreeSet里，但是还有一个简单的方法，就是我创建一个动态数组list，遍历一下num2，如果有set里的元素就把它存入list中 ，我们还需要多做一个操作就是删除掉存入的这个元素，这个就算在有重复的这个元素也不会存入这个动态数组中了。
• 最后，剩下的事情就很简单了，我们只需要吧list中的数放到数组中就可以了。
  更多精彩请关注公众号及时接收