两个数组的交集[数组]

链接：java中CopyOf的用法

题目描述

题目

实现思路

• 两个数组排序
• 判断两个数组谁比较小
• 在较大的数组中遍历一遍，寻找较小的数组中的数
• 找到相等的就保存起来，下标向后移动一位，下次遍历从本次的后一位开始。

代码版本(一) 通过率仅击败了14%

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int array1_size = nums1.length;
        int array2_size = nums2.length;
        boolean first_big = (array1_size>array2_size);
        ArrayList<Integer> list = new ArrayList<Integer>();
        if(first_big){
            int remember = 0;
            for(int i = 0;i < array2_size;i++){
                for(int j=remember;j<array1_size;j++){
                    if(nums1[j] == nums2[i]){
                        list.add(nums1[j]);
                        remember = j+1;
                        break;
                    }
                }
            }
        }
        else{
            int remember = 0;
            for(int i = 0;i < array1_size;i++){
                for(int j=remember;j<array2_size;j++){
                    if(nums2[j] == nums1[i]){
                        list.add(nums2[j]);
                        remember = j+1;
                        break;
                    }
                }
            }
        }
        int []reArray = new int[list.size()];
        for(int i = 0;i<list.size();i++){
            reArray[i] = list.get(i);
        }
        return reArray;
    }
}

通过情况

通过情况

改进思路

• 数组排序
• 设置两个遍历指针
• 创建一个数组用于保存交集
• 如果两个数相等，遍历指针都向后移一位
• 如果不想等，数值较小的那个数组遍历指针向后移动一位
• 当有一个数组越界时停止判断
• 复制当前返回数组的前K个，k为相等的数的个数

代码版本（二）

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int len1 = nums1.length;
        int len2 = nums2.length;
        int[] save = new int[len1 > len2 ? len1:len2];
        int i=0,j=0,k=0;
        while (i<len1 && j<len2){
            if(nums1[i]==nums2[j]) {
                save[k]=nums1[i];
                i++;j++;k++;
            }else if(nums1[i]<nums2[j]) {
                i++;
            }else {
                j++;
            }
        }
        return Arrays.copyOf(save, k);
    }
}

通过情况

通过

需要注意排序函数的使用，以及拷贝数组的使用