Semak sama ada tatasusunan boleh dimuatkan ke dalam tatasusunan lain dengan menyusun semula elemen dalam tatasusunan

Daripada huraian masalah, kita dapat memahami bahawa diberikan dua tatasusunan, kita perlu menyemak sama ada tatasusunan pertama boleh dimuatkan ke dalam tatasusunan kedua.

Dalam dunia nyata, terdapat banyak situasi di mana kita perlu menyemak sama ada tatasusunan boleh dimuatkan ke dalam tatasusunan lain dengan menyusun semula elemen dalam tatasusunan.

Atas pelbagai sebab, pengaturcara mungkin perlu menyusun semula item tatasusunan untuk melihat sama ada ia sesuai dengan tatasusunan lain. Pengurusan memori dalam pengaturcaraan komputer adalah salah satu daripadanya. Apabila bekerja dengan jumlah data yang besar, selalunya lebih cekap menggunakan tatasusunan untuk menyimpan data namun, disebabkan oleh had memori, tatasusunan mungkin perlu disusun dengan cara yang khusus untuk mengelakkan had ingatan.

Penjelasan

diterjemahkan sebagai:

Penjelasan

Mari cuba menyahkod soalan ini.

Katakan anda mempunyai dua tatasusunan: tatasusunan A mempunyai saiz n, dan tatasusunan B mempunyai saiz m, di mana m lebih besar daripada atau sama dengan n. Tugasnya adalah untuk menyemak sama ada mungkin untuk menyusun semula elemen tatasusunan A supaya tatasusunan A boleh terkandung sepenuhnya dalam tatasusunan B.

Dalam erti kata lain, setiap elemen tatasusunan A mesti ada dalam tatasusunan B dan dalam susunan yang sama seperti dalam tatasusunan A. Walau bagaimanapun, mungkin terdapat elemen tambahan dalam tatasusunan B yang tidak terdapat dalam tatasusunan A.

Sebagai contoh, katakan tatasusunan A mengandungi unsur [3,2,1] dan tatasusunan B mengandungi unsur [2, 1, 3, 4, 5]. Kita boleh menyusun semula elemen tatasusunan A untuk mendapatkan [3, 2, 1], yang kemudiannya boleh terkandung sepenuhnya dalam tatasusunan B seperti ditunjukkan di bawah −

Sebaliknya, jika tatasusunan A mengandungi elemen [1, 2, 3] dan tatasusunan B mengandungi elemen [2, 3, 4, 5], kita tidak boleh menyusun semula elemen tatasusunan A untuk dimuatkan sepenuhnya ke dalam tatasusunan B kerana dalam tatasusunan B Tiada unsur 1.

Jadi dalam kes ini fungsi yang menyemak sama ada tatasusunan A boleh dimuatkan ke dalam tatasusunan B dengan menyusun semula elemen akan mengembalikan Palsu.

Kaedah

Mari menyahkod keseluruhan program ke dalam algoritma langkah demi langkah.

• Isih dua tatasusunan ini dalam tertib menaik.

• Membandingkan elemen dua tatasusunan, bermula dari entri pertama setiap tatasusunan.

• Jika elemen tatasusunan yang lebih kecil adalah kurang daripada atau sama dengan elemen yang sepadan dalam tatasusunan yang lebih besar, teruskan beralih ke elemen seterusnya dalam kedua-dua tatasusunan.

• Jika elemen tatasusunan yang lebih kecil lebih besar daripada elemen yang sepadan dalam tatasusunan yang lebih besar, kembalikan "palsu" kerana tatasusunan yang lebih kecil tidak boleh dimuatkan dalam tatasusunan yang lebih besar.

• Mengembalikan "benar" jika semua item tatasusunan yang lebih kecil adalah kurang daripada atau sama dengan elemen yang sepadan dalam tatasusunan yang lebih besar, kerana tatasusunan yang lebih kecil boleh dimuatkan ke dalam tatasusunan yang lebih besar.

Nota− Disebabkan oleh langkah pengisihan, kerumitan algoritma ini ialah O(n log n), dengan n ialah saiz tatasusunan.

Contoh

Pelaksanaan kod C++: Semak sama ada tatasusunan boleh dimuatkan ke dalam tatasusunan lain dengan menyusun semula elemen dalam tatasusunan

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

bool can_fit(vector<int>& arr_1, vector<int>& arr_2) {

//base case
if(arr_1.size() > arr_2.size())
return false;

   // Sort both arrays
   sort(arr_1.begin(), arr_1.end());
   sort(arr_2.begin(), arr_2.end());
   
   // Check if arr_1 can fit into arr_2
   int i = 0, j = 0;
   while (i < arr_1.size() && j < arr_2.size()) {
      if (arr_1[i] <= arr_2[j]) {
         i++;
         j++;
      } else {
         return false;
      }
   }
   return true;
}

int main() {
   vector<int> A, B;
   A.push_back(2);
   A.push_back(5);
   A.push_back(7);
   A.push_back(9);
   A.push_back(10);
   B.push_back(1);
   B.push_back(3);
   B.push_back(5);
   B.push_back(7);
   B.push_back(9);
   B.push_back(9);
   B.push_back(10);

   // Check whether B can fit into A
   if (can_fit(A, B)) {
      cout << "Array A can fit into array B by rearranging the elements." << endl;
   } else {
      cout << "Array A cannot fit into Array B by rearranging the elements." << endl;
   }
   
   return 0;
}

Output

Array A cannot fit into array B by rearranging the elements.

Kerumitan

Kerumitan masa: O(n log n), kerana dalam kod ini, kita mula-mula mengisih dua tatasusunan dan kemudian melakukan lelaran.

Kerumitan ruang: O(n) kerana kami menyimpan elemen dua vektor dalam ingatan.

Kesimpulan

Dalam artikel ini, kami telah cuba menerangkan kaedah untuk menyemak sama ada tatasusunan boleh dimuatkan ke dalam tatasusunan lain. Harap artikel ini membantu anda memahami konsep ini dengan lebih baik.

Atas ialah kandungan terperinci Semak sama ada tatasusunan boleh dimuatkan ke dalam tatasusunan lain dengan menyusun semula elemen dalam tatasusunan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!