数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律学C++程序查找两个数组的公共元素
数组和数据结构的使用允许在多个内存位置存储同构（相同）数据。使用数组的主要优点是我们可以使用索引参数从任何我们想要的地方访问它们。数据必须按顺序添加和删除这一事实将这种数据结构转换为线性数据结构。要从数组中检索元素，我们只需要使用该元素在方括号内的索引或位置号即可。在本文中，我们将使用 C++ 获取两个数组，并仅查找这两个数组中存在的公共元素。
通过示例理解概念
Given first array A = [10, 14, 65, 85, 96, 12, 35, 74, 69] Given second array B = [23, 65, 89, 96, 12, 37, 71, 69] The common elements in arrays A and B are [65, 96, 12, 69]
第一个数组有九个元素，第二个数组有八个元素。因此，数组的大小可能不同。我们的任务是找到这两个数组之间的公共元素。在这里，我们将看到一些解决此问题的方法。
朴素解法
第一个也是最常见的解决方案是遍历第一个数组中的每个元素，并针对第一个数组的每个条目在第二个数组中搜索。此解决方案效率不高，但更简单。让我们看看算法和相应的实现。
算法
将两个数组 A 和 B 作为输入
定义另一个数组 D 以保存所有重复元素
对于 A 中的每个元素 e1，执行
对于 B 中的每个元素 e2，执行
如果 e1 = e2，则
将 e1 插入 D
结束if
结束for
结束for
返回 D
示例
#include <iostream>
# define Z 50
using namespace std;
void displayArr(int arr[], int n){
for( int i = 0; i < n; i++ ){
cout << arr[ i ] << ", ";
}
cout << endl;
}
void findCommonElement( int A[], int n, int B[], int m, int D[], int &k ) {
k = 0;
for( int i = 0; i < n; i++ ) {
for( int j = 0; j < m; j++ ) {
if( A[ i ] == B[ j ] ) {
D[ k ] = A[ i ];
k = k + 1;
}
}
}
}
int main() {
int A[ Z ] = { 10, 14, 65, 85, 96, 12, 35, 74, 69 };
int n = 9;
int B[ Z ] = { 23, 65, 89, 96, 12, 37, 71, 69 };
int m = 8;
int D[ Z ];
int k = 0;
cout << "Given first array A: ";
displayArr( A, n );
cout << "Given second array B: ";
displayArr( B, m );
findCommonElement( A, n, B, m, D, k );
cout << "The common elements are: ";
displayArr( D, k );
}
输出
Given first array A: 10, 14, 65, 85, 96, 12, 35, 74, 69, Given second array B: 23, 65, 89, 96, 12, 37, 71, 69, The common elements are: 65, 96, 12, 69,
使用向量和 set_intersection() 函数
set_intersection() 函数随 C++ STL 提供。使用此方法，公共元素将作为迭代器对象返回。但要使用此函数，我们必须按升序对数组进行排序。让我们看看算法和 C++ 实现代码。
算法
将两个数组 A 和 B 作为输入
定义另一个数组 D 以保存所有重复元素
为重复元素数组创建迭代器
使用set_intersection() 方法结合 A 和 B 数组，并将结果存储在 D 数组中
返回 D
示例
#include <iostream>
#include <algorithm>
#include <vector>
# define Z 50
using namespace std;
void displayArr( vector<int> v ){
for( int i = 0; i < v.size() ; i++ ){
cout << v[ i ] << ", ";
}
cout << endl;
}
vector<int> findCommonElement( vector<int> A, vector<int> B ) {
sort( A.begin(), A.end() );
sort( B.begin(), B.end() );
vector<int> duplicates;
vector<int> D( A.size() + B.size() );
vector<int>::iterator Dit, st;
Dit = set_intersection( A.begin(), A.end(), B.begin(), B.end(), D.begin() );
for( st = D.begin(); st != Dit; ++st )
duplicates.push_back( *st ) ;
return duplicates;
}
int main() {
vector<int> A = { 10, 14, 65, 85, 96, 12, 35, 74, 69 };
vector<int> B = { 23, 65, 89, 96, 12, 37, 71, 69 };
vector<int> D;
cout << "Given first array A: ";
displayArr( A );
cout << "Given second array B: ";
displayArr( B );
D = findCommonElement( A, B );
cout << "The common elements are: ";
displayArr( D );
}
输出
Given first array A: 10, 14, 65, 85, 96, 12, 35, 74, 69, Given second array B: 23, 65, 89, 96, 12, 37, 71, 69, The common elements are: 12, 65, 69, 96,
结论
在本文中，我们看到了两种从元素集或两个数组中查找公共元素的方法。第一个朴素解决方案采用两个静态数组，并通过逐个扫描每个元素来查找公共元素。此解决方案需要 O(n.m) 时间，其中 n 是第一个数组的大小，m 是第二个数组的大小。下一种方法使用基于 C++ STL 的 set_intersection() 方法。在这种方法中，我们需要使用排序后的向量。之后，该方法将返回公共元素迭代器的迭代器对象。我们可以从中创建一个向量并返回它。
5K+ 次查看
