349. 两个数组的交集

leetcode链接：
https://leetcode.cn/problems/intersection-of-two-arrays/

方案一

暴力求解

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

        List<Integer> result = new ArrayList<Integer>();

        for (int i = 0; i < nums1.length; i++) {
            for (int j = 0; j < nums2.length; j++) {
                if (nums1[i] == nums2[j] && !result.contains(nums2[j])) {
                    result.add(nums1[i]);
                }
            }
        }

        // 因为int数组不是对象，其需要传入一个是对象的数组，所以使用Integer
        Integer[] array = result.toArray(new Integer[result.size()]);

        // JDK8,通过Stream流来实现Integer数组向int数组转化
        return Arrays.stream(array).mapToInt(Integer::valueOf).toArray();
    }
}

结果

解答成功:
执行耗时:10 ms,击败了5.07% 的Java用户
内存消耗:41.1 MB,击败了98.26% 的Java用户

分析

时间复杂度：
O( n * m )

空间复杂度：
O( n + m )

方案二

先排序，再查找，双指针

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        List<Integer> result = new ArrayList<>();

        Arrays.sort(nums1);
        Arrays.sort(nums2);

        int nums1Size = nums1.length, nums2Size = nums2.length, nums1Flag = 0, nums2Flag = 0;

        for (;;) {
            if (nums1[nums1Flag] > nums2[nums2Flag]) {
                nums2Flag++;
            } else if (nums1[nums1Flag] == nums2[nums2Flag] && !result.contains(nums1[nums1Flag])) {
                result.add(nums1[nums1Flag]);
            } else {
                nums1Flag++;
            }

            if (nums1Flag == nums1Size || nums2Flag == nums2Size)
                break;
        }

        Integer[] array = result.toArray(new Integer[result.size()]);
        return Arrays.stream(array).mapToInt(Integer::valueOf).toArray();
    }
}

结果

解答成功:
执行耗时:6 ms,击败了7.57% 的Java用户
内存消耗:41.1 MB,击败了96.65% 的Java用户

官方解答

https://leetcode.cn/problems/intersection-of-two-arrays/solution/liang-ge-shu-zu-de-jiao-ji-by-leetcode-solution/

此回答中的方法二：排序 + 双指针，思想与方案二很相似，细节处理不同

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int length1 = nums1.length, length2 = nums2.length;
        int[] intersection = new int[length1 + length2];
        int index = 0, index1 = 0, index2 = 0;
        while (index1 < length1 && index2 < length2) {
            int num1 = nums1[index1], num2 = nums2[index2];
            if (num1 == num2) {
                // 保证加入元素的唯一性
                if (index == 0 || num1 != intersection[index - 1]) {
                    intersection[index++] = num1;
                }
                index1++;
                index2++;
            } else if (num1 < num2) {
                index1++;
            } else {
                index2++;
            }
        }
        return Arrays.copyOfRange(intersection, 0, index);
    }
}

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/intersection-of-two-arrays/solution/liang-ge-shu-zu-de-jiao-ji-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。