Program C++ untuk mencari elemen biasa daripada dua tatasusunan

Gunakan tatasusunan dan struktur data untuk menyimpan data homogen (sama) pada berbilang lokasi memori. Kelebihan utama menggunakan tatasusunan ialah kita boleh mengaksesnya dari mana-mana sahaja dengan menggunakan parameter indeks. Fakta bahawa data mesti ditambah dan dialih keluar secara berurutan menjadikan struktur data ini menjadi struktur linear. Untuk mendapatkan semula elemen daripada tatasusunan, kita hanya perlu menggunakan indeks atau nombor kedudukan di dalam kurungan segi empat sama. Dalam artikel ini, kami akan menggunakan C++ untuk mendapatkan satu-satunya elemen biasa yang terdapat dalam dua tatasusunan.

Fahami konsep dan gambarkan dengan contoh

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]

Dalam tatasusunan pertama, terdapat sembilan elemen dan dalam tatasusunan kedua, terdapat lapan elemen. Jadi kedua-dua tatasusunan mungkin tidak sama saiz. Tugas kami adalah untuk mencari elemen sepunya antara dua tatasusunan ini. Di sini kita akan melihat beberapa petua untuk menyelesaikan masalah ini.

Penyelesaian naif

Penyelesaian pertama dan paling biasa adalah untuk menggelung melalui setiap elemen tatasusunan pertama dan mencari dalam tatasusunan kedua untuk setiap entri tatasusunan pertama. Penyelesaian ini kurang cekap, tetapi lebih mudah. Mari kita lihat algoritma dan pelaksanaan yang sepadan.

Algoritma

• Ambil dua tatasusunan A dan B sebagai input

• Tentukan tatasusunan lain D untuk memegang semua elemen berulang

• Untuk setiap elemen e1 dalam A, lakukan perkara berikut

  • Untuk setiap elemen e2 dalam B, lakukan perkara berikut

    • Jika e1 = e2, maka

      • Masukkan e1 ke dalam D

    • Tamat jika

  • Tamatkan kitaran

• Tamatkan kitaran

• Kembali ke D

Terjemahan bahasa Cina bagi

Contoh

ialah:

Contoh

#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 ); 
}

Output

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,

Gunakan vektor dan fungsi set_intersection()

Menggunakan C++ STL, fungsi set_intersection() mengembalikan elemen biasa sebagai objek lelaran. Tetapi untuk menggunakan fungsi ini kita perlu mengisih tatasusunan dalam tertib menaik. Mari kita lihat algoritma dan kod pelaksanaan C++.

Algoritma

• Ambil dua tatasusunan A dan B sebagai input

• Tentukan tatasusunan lain D untuk memegang semua elemen berulang

• Buat iterator untuk susunan elemen berulang

• Gunakan kaedah set_intersection() untuk melaksanakan operasi persilangan pada tatasusunan A dan B dan simpan hasilnya dalam tatasusunan D

• Kembali ke D

Terjemahan bahasa Cina bagi

Contoh

ialah:

Contoh

#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 ); 
}

Output

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,

Kesimpulan

Dalam artikel ini, kami melihat dua cara untuk mencari elemen biasa daripada koleksi elemen atau dua tatasusunan. Penyelesaian naif pertama ialah menggunakan dua tatasusunan statik dan mencari elemen biasa dengan mengimbas setiap elemen satu demi satu. Kerumitan masa penyelesaian ini ialah O(n.m), di mana n ialah saiz tatasusunan pertama dan m ialah saiz tatasusunan kedua. Kaedah seterusnya menggunakan kaedah set_intersection() berasaskan C++ STL. Dalam kaedah ini kita perlu menggunakan vektor yang diisih. Kaedah itu kemudian mengembalikan objek lelaran elemen awam. Kita boleh mencipta vektor daripadanya dan mengembalikannya.

Atas ialah kandungan terperinci Program C++ untuk mencari elemen biasa daripada dua tatasusunan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!