LeetCode - 两个数组的交集

晓痴

发布于 2019-10-08 15:03:22

8970

发布于 2019-10-08 15:03:22

文章被收录于专栏：曌的晓痴曌的晓痴

原题地址：https://leetcode-cn.com/problems/intersection-of-two-arrays/

题目描述：

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

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

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

说明:

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

来源：力扣（LeetCode）

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

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路：

这个也有几种方法：

变成两个Set，然后分别用removeAll()和retainAll()的方式去判断是否存在交集，需要空间和时间。
直接遍历两个数组，判断数字是否在对方的数组内，时间复杂度肯定是O(n^2)
先对数组进行排序，然后对两个数组进行一次遍历。遍历过程中，比较两者大小，谁小就移动谁的指针。直到两个数组中任一数组遍历完成，就退出循环。最后返回遍历过程中，相等的元素。时间复杂度依据数组情况而定。

我用的是最复杂的方式。

中文官网题解：

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

个人题解：

public class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        List<Integer> result = new ArrayList<Integer>();
        int i = 0, j = 0;
        while (i < nums1.length && j < nums2.length) {
            int n1 = nums1[i];
            int n2 = nums2[j];
            if (n1 == n2) {
                boolean flag = false;
                for(Integer k : result){
                    if(k == n1)
                        flag = true;
                }
                if(flag == false)
                    result.add(n1);
                i++;
                j++;
            } else if (n1 < n2)
                i++;
            else
                j++;
        }
        int[] ret = new int[result.size()];
        int k = 0;
        for (int num : result)
            ret[k++] = num;
        return ret;
    }
}

结果：

运行结果一般。