LeetCode_排序_简单_349.两个数组的交集

目录

• 1.题目
• 2.思路
• 3.代码实现（java）

1.题目

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

示例 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

2.思路

（1）排序+双指针

（1.1）创建一个长度为nums1.length+nums2.length的数组res，用来保存结果，并且对数组nums1和nums2进行排序；

（1.2）定义变量i、j、k，其初始值均为0，其中i和j分别用来遍历数组nums1和nums2，k表示即将添加到数组res的元素下标；

（1.3）同时遍历数组nums1和nums2：

若nums1[i]=nums2[j]，且k=0或nums1[i]!=res[k-1]时，将nums1[i]添加到res中，并且指针i和j同时向后移动一位；

若nums1[i]<nums2[j]，指针i向后移动一位；

若nums1[i]>nums2[j]，指针j向后移动一位；

（1.4）遍历结束后，将数组res中下标为0~k-1的部分返回即可。

3.代码实现（java）

//（1）排序+双指针
public int[] intersection(int[] nums1, int[] nums2) {
    int len1=nums1.length;
    int len2=nums2.length;
    int[] res=new int[len1+len2];
    //对数组nums1和nums2进行排序
    Arrays.sort(nums1);
    Arrays.sort(nums2);
    int i=0,j=0,k=0;
    while(i<len1 && j<len2){
        if(nums1[i]==nums2[j]){
            //保证交集的互异性
            //若k==0，说明res中暂时还未添加添加元素，此时可以直接添加而不会使得元素重复；
            /*由于数组nums1和nums2都是经过排序了的，所以数组res中依次添加的元素肯定都是有序的，当k!=0但nums1[i]!=res[k-1]时，
              这说明当前元素nums1[i]肯定不在res中，所以也可以直接添加；若k!=0但nums1[i]==res[k-1]时，说明数组res中已经添加过了
              nums1[i]，此时不需要再重复添加nums1[i]。
			*/
            if(k==0 || nums1[i]!=res[k-1]){
                res[k++]=nums1[i];
            }
            i++;
            j++;
        }else if(nums1[i]<nums2[j]){
            i++;
        }else{
            j++;
        }
    }
    //Arrays.copyOfRange(T[] ori,int from,int to):将原始数组ori从下标from开始(包括)复制，复制到上标to(不包括)，生成一个新的数组
    return Arrays.copyOfRange(res,0,k);
}