当前位置：首页 > news >正文

【每日一题】王道 - 求序列公共元素

news 2025/4/21 23:42:45

在算法与数据结构的学习中，我们常常会遇到寻找多个序列间公共元素的问题。这类问题不仅考察算法效率，还要求对基本的数据结构有深刻理解。今天，我们将讨论一个求三序列公共元素的经典问题，并提供两种解法：暴力法和双指针法。

如果你不清楚什么是双指针法可以看我另外的一篇博客

【数据结构】双指针算法：理论与实战

问题描述

给定三个等长递增序列 A、B、C，这些序列长度均为 n，且元素无重复。我们的任务是设计一个尽可能高效的算法，找出这三个序列中的公共元素。

示例

数组 A = {1, 2, 3}
数组 B = {2, 3, 4}
数组 C = {-1, 0, 2}

输出：2

解题思路

这道题涉及在多个序列中查找公共元素。由于题目限制了序列是递增且无重复元素，因此我们可以利用这些性质来减少不必要的比较，从而优化效率。

解法一：暴力法

思路

暴力法的想法非常直接：使用三重循环来遍历 A、B、C 的所有可能组合，检查每个组合的元素是否相等。若相等，则记录该元素为公共元素。虽然这种方法简单，但它的时间复杂度较高。

实现代码

#include <iostream>
#include <vector>
#include <set>using namespace std;vector<int> findCommonBruteForce(vector<int> a, vector<int> b, vector<int> c) {vector<int> res;set<int> seen; // 用于避免重复元素for (int i = 0; i < a.size(); i++) {for (int j = 0; j < b.size(); j++) {for (int k = 0; k < c.size(); k++) {if (a[i] == b[j] && b[j] == c[k]) {// 若公共元素未被添加到结果集中，添加它if (seen.find(a[i]) == seen.end()) {res.push_back(a[i]);seen.insert(a[i]);}}}}}return res;
}int main() {vector<int> a = {1, 2, 3};vector<int> b = {2, 3, 4};vector<int> c = {-1, 0, 2};vector<int> ans = findCommonBruteForce(a, b, c);for (auto r : ans) {cout << r << endl;}return 0;
}

时间复杂度分析

暴力法的时间复杂度为 $O(n^3) )$ ，其中 n 为数组的长度。三重循环导致算法在处理较大数组时效率较低。

解法二：双指针法

思路

由于 A、B、C 均为递增序列，我们可以利用双指针技术提高效率。具体来说，我们使用三个指针分别遍历 A、B 和 C，并在每个数组上逐步移动指针：

若 A[q] == B[w] == C[e]，则将该元素加入结果。
若 A[q] < B[w]，则移动 A 的指针 q++，以尝试找到更大的匹配元素。
若 B[w] < C[e]，则移动 B 的指针 w++。
否则，移动 C 的指针 e++。

该方法有效地利用了排序数组的特性，从而大大减少了不必要的比较。

实现代码

vector<int> find(vector<int> a, vector<int> b, vector<int> c) {vector<int> res;int q = 0, w = 0, e = 0;while (q < a.size() && w < b.size() && e < c.size()) {if (a[q] == b[w] && b[w] == c[e]) {res.push_back(a[q]);q++;w++;e++;} else if (a[q] < b[w]) q++;else if (b[w] < c[e]) w++;else e++;}return res;
}int main() {vector<int> a = {1, 2, 3};vector<int> b = {2, 3, 4};vector<int> c = {-1, 0, 2};vector<int> ans = find(a, b, c);for (auto r : ans) {cout << r << endl;}return 0;
}