【LeetCode】第39天 - 350. 两个数组的交集 II

x33g5p2x  于2022-02-24 转载在 其他  
字(0.8k)|赞(0)|评价(0)|浏览(170)

题目描述

解题思路

  • 1.先将两个数组排序;
  • 2.然后用两个指针分别遍历两个数组,双指针的移动规则如下:
    初始时,两个指针分别指向数组的头部。每次遍历比较两个指针所在位置的值,如果相等则将该值加入结果数组中(交集),同时将两个指针都向后移动一位;如果不等,则将较小值的指针向后移动一位。
  • 3.直到两个数组中的一个遍历完成,则结束遍历。

代码实现

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);     //对nums1排序
        Arrays.sort(nums2);     //对nums2排序

        //创建一个数组存放交集
        int length1 = nums1.length,length2 = nums2.length;
        int[] temp = new int[length1>length2?length2:length1];

        /**
         * index1 :遍历nums1的指针
         * index2 :遍历nums2的指针
         * count : 记录交集的个数
         */
        int index1 = 0,index2 = 0,count = 0;
        
        //当nums1或nums2遍历完时,结束循环
        while(index1<length1 && index2 <length2){
            if(nums1[index1] == nums2[index2]){     //获取到交集
                temp[count] = nums1[index1];        //放入temp中
                ++count;
                ++index1;
                ++index2;
            }else if(nums1[index1] < nums2[index2]){        //nums1[]小,index1后移一位
                ++index1;
            }else{          //nums2[]小,index2后移一位
                ++index2;
            }
        }

        //返回temp中的前count个元素
        return Arrays.copyOfRange(temp,0,count);
    }
}

相关文章

微信公众号

最新文章

更多