資料結構
網路
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+ 次檢視
