IntersectionOfTwoArrays [source code]

public class IntersectionOfTwoArrays {
    public int[] intersection(int[] nums1, int[] nums2) {
        if (nums1.length < nums2.length) {
            int[] tmp = nums2;
            nums2 = nums1;
            nums1 = tmp;
        }
        Set<Integer> set1 = new HashSet<>();
        for (int i : nums1) set1.add(i);
        Set<Integer> res = new HashSet<>();
        for (int i : nums2) {
            if (set1.contains(i)) {
                res.add(i);
            }
        }
        int[] ret = new int[res.size()];
        int end = 0;
        for (int i : res) ret[end++] = i;
        return ret;
    }
}

算法总体来说还是很简单的, 就是一个暴力搜. 一个稍微值得一提的小技巧: 把较长的nums 放在 set 里面, 因为 set 的查询是比普通的 linear 快的, 所以把较大的 set 作为 dictionary 相对来说节省的 cost 比较多; //事实证明并没有区别, 我换了一下, 结果两个速度是一模一样的;

速度是6ms, 49%;

值得一提的一个东西: 一开始想要这么写:

         return (int[]) res.toArray(new Integer[0]);

但是好像不行, Integer[] to int[]的 cast 看了一下, 好像未必比较好的 API 做法涉及到 JAVA8的 stream, 这个就很麻烦了, 所以干脆就直接手动来左算了;

Problem Description

Given two arrays, write a function to compute their intersection.

Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].

Note:
Each element in the result must be unique.
The result can be in any order.
Difficulty:Easy
Category:Algorithms
Acceptance:46.97%
Contributor: LeetCode
Companines
Two Sigma
Related Topics
binary search hash table two pointers sort
Similar question
Intersection of Two Arrays II