LeetCode刷题实战349：两个数组的交集-轻识

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 两个数组的交集，我们先来看题面：

https://leetcode-cn.com/problems/intersection-of-two-arrays/

Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must be unique and you may return the result in any order.

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

示例

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]

示例 2：

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

解题

解法一：set

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        // set
        Set<Integer> set = new HashSet<>();
        // 对nums1数组进行排序
        Arrays.sort(nums1);
        // 遍历nums2的每个元素
        for (int num2 : nums2) {
            // 对比nums1中的元素
            for (int num1 : nums1) {
                // 相等保存到set中
                if (num1 == num2) {
                    set.add(num1);
                    break;
                }
                // 如果num1已经大于num2，说明这个数不是交集，跳出循环
                if (num1 > num2) {
                    break;
                }
            }
        }

        // 转成数组
        int[] ret = new int[set.size()];
        int i = 0;
        for (int num : set) {
            ret[i++] = num;
        }
        return ret;
    }
}

解法二：二分查找法

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        // 二分查找
        // 对nums1数组进行排序
        Arrays.sort(nums1);

        Set<Integer> set = new HashSet<>();
        // 遍历nums2数组
        for (int target : nums2) {

            // 每个元素都到nums1数组中二分查找
            int l = 0, r = nums1.length - 1;
            while (l <= r) {
                // 取中位下标
                int mid = l + (r - l) / 2;
                if (target < nums1[mid]) {
                    r = mid - 1;
                } else if (target > nums1[mid]) {
                    l = mid + 1;
                } else {
                    // 相等，保存到set中
                    set.add(target);
                    break;
                }
            }

        }

        // 转成数组
        int[] ret = new int[set.size()];
        int i = 0;
        for (int num : set) {
            ret[i++] = num;
        }
        return ret;
    }
}

解法三：双set

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        // 双set
        Set<Integer> set1 = new HashSet<>();
        Set<Integer> set2 = new HashSet<>(); // 存放交集元素
        // 先把nums1数组的所有元素放到set中
        for (int num : nums1) {
            set1.add(num);
        }

        // 遍历nums2数组，如果nums2的元素存在于set1中，放入set2中
        for (int num : nums2) {
            if (set1.contains(num)) {
                set2.add(num);
            }
        }

        // 转成数组
        int[] ret = new int[set2.size()];
        int i = 0;
        for (int num : set2) {
            ret[i++] = num;
        }
        return ret;
    }
}