349. 两个数组的交集

Posted on | In
Words count in article: 478 | Reading time ≈ 2

题目

给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

示例1：

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

示例2：

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

提示:

  • 1 <= nums1.length, nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 1000

解法

解法一：

使用一个HashSet

数组中元素不是唯一的，因此，两个数组的交集可能存在不唯一的数字，因此，使用了一个HashSet来去重。
整体思路是将两个数组排序，从第一个开始对比，如果相等，则同时进1，如果A[indexA] > B[indexB]，则B索引进1,否则A索引进1。

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
		Arrays.sort(nums1);
		Arrays.sort(nums2);
		
		int length1 = 0;
		int length2 = 0;

		HashSet<Integer> result = new HashSet<>();
		
		while (length1 < nums1.length && length2 < nums2.length) {
			if (nums1[length1] == nums2[length2]) {
				result.add(nums1[length1]);
				length1++;
				length2++;
			} else if (nums1[length1] < nums2[length2]) {
				length1++;
			} else {
				length2++;
			}
		}
		
		int array[] = new int[result.size()];
		int i = 0;
		for (int value : result) {
			array[i] = value;
			i++;
		}
		
		return array;
    }
}

解法二：

使用两个HashSet

将nums1和nums2的数据都保存到set1和set2中，然后利用HashSet的retainAll方法，求它们的交集，输出即可。

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int[] intersection(int[] nums1, int[] nums2) {
		HashSet<Integer> set1 = new HashSet<>(nums1.length);
		HashSet<Integer> set2 = new HashSet<>(nums2.length);
		
		for (int num : nums1) {
			set1.add(num);
		}
		
		for (int num : nums2) {
			set2.add(num);
		}
		
		set1.retainAll(set2);
		
		return set1.stream().mapToInt(a -> a).toArray();
	}

解法三：

对nums1进行排序，然后遍历nums2，对每个在nums2中的数字，在nums1中二分查找，存在就保存到set中。

Java

1
2
3
4
5
6
7
8
9
10
11
public int[] intersection(int[] nums1, int[] nums2) {
		HashSet<Integer> set = new HashSet<>();
		Arrays.sort(nums1);
		for (int num : nums2) {
			if (0 <= Arrays.binarySearch(nums1, num)) {
				set.add(num);
			}
		}
		
		return set.stream().mapToInt(a -> a).toArray();
	}
0%