题目描述
给出三个均为 严格递增排列 的整数数组 arr1
,arr2
和 arr3
。
返回一个由 仅 在这三个数组中 同时出现 的整数所构成的有序数组。
样例
输入: 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
算法
(暴力枚举) $O(n_1 + n_2 + n_3)$
- 由于三个数组已经是排好序的,所以我们用三个指针分别从头指向这三个数组,然后依次遍历。
- 如果当前这三个指针指向的数字相同,则加入到答案数组中,三个指针依次后移。
- 否则,我们找到三个指针中最小的元素,移动所有和这个最小元素相同的指针。
- 当其中一个指针到达末尾后,退出循环。
时间复杂度
- 每个元素最多遍历一次,故时间复杂度为 $O(n_1 + n_2 + n_3)$。
空间复杂度
- 仅需常数的额外空间。
C++ 代码
class Solution {
public:
vector<int> arraysIntersection(vector<int>& arr1, vector<int>& arr2, vector<int>& arr3) {
int n1 = arr1.size(), n2 = arr2.size(), n3 = arr3.size();
vector<int> ans;
int i = 0, j = 0, k = 0;
while (i < n1 && j < n2 && k < n3) {
if (arr1[i] == arr2[j] && arr2[j] == arr3[k]) {
ans.push_back(arr1[i]);
i++; j++; k++;
} else {
int minx = min(arr1[i], min(arr2[j], arr3[k]));
if (minx == arr1[i])
i++;
if (minx == arr2[j])
j++;
if (minx == arr3[k])
k++;
}
}
return ans;
}
};