By

前言

Github：https://github.com/HealerJean

博客：http://blog.healerjean.com

1、两个数组的交集1

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

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]

示例 2：

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]

1.1、解题思路

集合解决

1.2、算法

public int[] intersection(int[] nums1, int[] nums2) {
    List<Integer> list = Arrays.stream(nums1).mapToObj(Integer::new).collect(Collectors.toList());
    Set<Integer> set = new HashSet<>();
    for (int num : nums2) {
        if (list.contains(num)) {
            set.add(num);
        }
    }
    return set.stream().mapToInt(Integer::intValue).toArray();
}

1.3、测试

@Test
public void test() {
    int[] nums1 = {4, 9, 5};
    int[] nums2 = {9, 4, 9, 8, 4};

    System.out.println(Arrays.toString(intersection(nums1, nums2)));
}

2、两个数组的交集2

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

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]

示例 2:

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[4,9]

2.1、解题思路

1、集合

2、先排序，再移动指针

2.2、算法

2.2.1、算法1

/**
* list解决
*/
public int[] intersect1(int[] nums1, int[] nums2) {
    List<Integer> list = Arrays.stream(nums1).mapToObj(Integer::new).collect(Collectors.toList());
    List<Integer> resList = new ArrayList<>();
    for (int num : nums2){
        if (list.contains(num)){
            list.remove((Integer)num);
            resList.add(num);
        }
    }
    return resList.stream().mapToInt(Integer::intValue).toArray();
}

2.2.2、算法2


/**
* 排序，移动指针，有点像合并有序数组
*/
public int[] intersect(int[] nums1, int[] nums2) {

    Arrays.sort(nums1);
    Arrays.sort(nums2);
    int i = 0 , j = 0 ;
    int count = 0 ;
    int[] res = new int[nums1.length + nums1.length];
    while (i < nums1.length && j < nums2.length){
        if (nums1[i] == nums2[j]){
            res[count] = nums1[i];
            i++ ;
            j++ ;
            count++;
        }else if (nums1[i] < nums2[j]){
            i++;
        }else {
            j++;
        }
    }
    return Arrays.copyOfRange(res, 0, count);
}

2.3、测试

@Test
public void test() {
    int[] nums1 = {4};
    int[] nums2 = {9};

    System.out.println(Arrays.toString( intersect(nums1, nums2)));
}

​

ContactAuthor