1213. 三个有序数组的交集

Posted on | In
Words count in article: 382 | Reading time ≈ 1

题目

给出三个均为 严格递增排列 的整数数组 arr1，arr2 和 arr3。

返回一个由 仅 在这三个数组中 同时出现 的整数所构成的有序数组。

示例1：

1
2
3
输入: arr1 = [1,2,3,4,5], arr2 = [1,2,5,7,9], arr3 = [1,3,4,5,8]
输出: [1,5]
解释: 只有 1 和 5 同时在这三个数组中出现.

提示：

  • 1 <= arr1.length, arr2.length, arr3.length <= 1000
  • 1 <= arr1[i], arr2[i], arr3[i] <= 2000

解法

解法一：

三指针

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
public List<Integer> arraysIntersection(int[] arr1, int[] arr2, int[] arr3) {
		List<Integer> res = new ArrayList<>();
		int arr1Index = 0;
		int arr2Index = 0;
		int arr3Index = 0;
		while (arr1Index < arr1.length && arr2Index < arr2.length && arr3Index < arr3.length) {
			if (arr1[arr1Index] == arr2[arr2Index] && arr2[arr2Index] == arr3[arr3Index]) {
				res.add(arr1[arr1Index]);
				arr1Index++;
				arr2Index++;
				arr3Index++;
				continue;
			}
			/// 最小值往后移动
			int minVal = Math.min(Math.min(arr1[arr1Index], arr2[arr2Index]), arr3[arr3Index]);
			if (arr1[arr1Index] == minVal) {
				arr1Index++;
			}
			if (arr2[arr2Index] == minVal) {
				arr2Index++;
			}
			if (arr3[arr3Index] == minVal) {
				arr3Index++;
			}
		}
		return res;
	}

解法二：

计数

因为题目限制了值最大不会超过2000。那么就可以声明一个2001长度的数组。

如果一个数字在每个数组中都出现过，那么，它的计数一定是3

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public List<Integer> arraysIntersection(int[] arr1, int[] arr2, int[] arr3) {
		List<Integer> result = new ArrayList<>();
		
		int[] count = new int[2001];
		count(arr1, count);
		count(arr2, count);
		count(arr3, count);
		
		for (int i = 0;i < count.length;i++) {
			if (3 == count[i]) {
				result.add(i);
			}
		}
		
		return result;
	}
	
	private void count(int[] array, int[] count) {
		for (int num : array) {
			count[num]++;
		}
	}
0%