C++程序从两个数组中查找公共元素-C++-PHP中文网

C++程序从两个数组中查找公共元素

WBOY

发布： 2023-09-09 23:13:09

转载

1339人浏览过

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作为输入

立即学习“C++免费学习笔记（深入）”；
定义另一个数组 D 来保存所有重复的元素
对于A中的每个元素e1，执行以下操作
- 对于B中的每个元素e2，执行以下操作
  - 如果 e1 = e2，则
    - 将 e1 插入到 D 中
  - 结束如果
- 结束循环
结束循环
返回 D

Example

的中文翻译为：

示例

#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()函数

使用C++ STL，set_intersection()函数返回公共元素作为迭代器对象。但是要使用此函数，我们必须将数组按升序排序。让我们来看看算法和C++实现代码。

算法

将两个数组A和B作为输入

立即学习“C++免费学习笔记（深入）”；
定义另一个数组 D 来保存所有重复的元素
为重复元素数组创建一个迭代器
使用 set_intersection() 方法将 A 和 B 数组进行交集运算，并将结果存储在 D 数组中
返回 D

Example

的中文翻译为：

示例

#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()方法。在这种方法中，我们需要使用排序后的向量。然后，该方法返回一个公共元素迭代器对象。我们可以从中创建一个向量并返回它。

以上就是C++程序从两个数组中查找公共元素的详细内容，更多请关注php中文网其它相关文章！