Semak sama ada tatasusunan yang diberikan boleh membentuk pilih atur daripada 1 hingga N dengan mengurangkan separuh unsur

Matlamat kami adalah untuk menentukan sama ada melakukan berbilang pembahagian pada setiap item yang terkandung dalam tatasusunan mencipta senarai integer dari 1 hingga N tanpa sebarang pendua. Kejayaan usaha ini bermakna matlamat penyiasatan kami telah berjaya dicapai. Pada asasnya, menentukan sama ada memotong semua elemen yang disediakan dalam tatasusunan tertentu dengan dua akan menghasilkan pilih atur yang terdiri sepenuhnya daripada nilai tidak berulang antara 1 dan N adalah fokus utama kerja kami. Setelah disahkan, menilai kertas kami akan menjadi langkah logik seterusnya.

Tatabahasa

Sebelum mendalami cadangan penyelesaian kami, adalah penting untuk memahami secara kasar sintaks kaedah yang akan kami laksanakan.

bool canBePermutation(vector<int>& arr)
{
   // Implementation goes here
}
</int>

Algoritma

Untuk menyelesaikan masalah ini, mari kita teruskan langkah demi langkah menggunakan algoritma yang digariskan di bawah -

• Untuk memberi perhatian yang teliti kepada komponen yang diperhatikan dalam tatasusunan, mulakan dengan memulakan koleksi atau set cincang. Kemudian, ulangi setiap elemen yang terdapat dalam tatasusunan itu.

• Untuk mendapatkan integer antara 1 dan N, anda perlu membahagikan setiap elemen dengan 2 beberapa kali.

• Semak sama ada nilai hasil sudah wujud dalam koleksi. Jika ya, mengembalikan palsu kerana tidak boleh ada pendua dalam susunan.

• Agar tatasusunan menjadi susunan yang sah, setiap elemen mesti memenuhi syarat di atas. Dengan mengandaikan kriteria ini dipenuhi sepenuhnya, mengesahkan kelayakannya dengan memberikan nilai pulangan sebenar boleh dianggap sebagai tindakan yang sesuai.

Kaedah

Untuk menyelesaikan masalah ini dengan berkesan. Ia mungkin berguna untuk meneroka strategi yang berbeza. Saya akan mencadangkan dua pendekatan yang mungkin -

Kaedah 1: Pendekatan berasaskan set

Mencipta pendekatan yang cekap memerlukan penggunaan teknik yang teliti, seperti melaksanakan sistem pengesanan menggunakan koleksi yang dicipta untuk merekodkan komponen yang dihadapi sepanjang proses. Ia melibatkan penilaian berulang setiap komponen melalui proses pembahagian, memastikan bahawa nilai yang terhasil jatuh di antara nilai julat 1 dan N, kemudian menyemak set surih kami untuk pengesahan sebelum menambahkan item yang baru diperhatikan, dan kemudian mengembalikan jika terdapat sebarang anomali palsu, sebaliknya mengembalikan benar apabila semua nilai telah melepasi semakan penilaian yang diperlukan oleh Constellation.

Contoh

#include <iostream>
#include <vector>
#include <unordered_set>

bool canBePermutation(std::vector<int>& arr) {
   std::unordered_set<int> seen;
   
   for (int num : arr) {
      while (num > 0 && num != 1) {
         if (seen.find(num) != seen.end())
            return false;
         
         seen.insert(num);
         num /= 2;
      }
      
      if (num == 0)
         return false;
   }
   
   return true;
}

int main() {
   std::vector<int> arr = {4, 2, 1, 3};
   
   if (canBePermutation(arr)) {
      std::cout << "The given array can be transformed into a permutation.";
   } else {
      std::cout << "The given array cannot be transformed into a permutation.";
   }
   
   return 0;
}

Output

The given array cannot be transformed into a permutation.

Arahan

Langkah awal kaedah 1 melibatkan menyediakan set tidak tertib untuk menjejaki elemen yang terdapat dalam tatasusunan. Kaedah pengekodan ini kemudiannya terus berulang ke atas setiap elemen dalam tatasusunan yang sama, membahagikannya dengan 2 setiap kali, berulang kali mengurangkannya kepada integer antara 1 dan N. Semasa lelaran ini, semakan dibuat untuk melihat sama ada item yang kelihatan telah dibuat telah dibuat dalam koleksi yang sama dengan itu cuba mengelakkan pilih atur pendua hanya disebabkan oleh pendua. Apabila pendua yang terhasil daripada pilih atur berulang ini dikesan, palsu dikembalikan, seperti apabila semuanya diperiksa tanpa pendua dilengkapkan - diluluskan sebagai benar - dengan berkesan menunjukkan sama ada set yang diberikan boleh dialihkan ke pilih atur masing-masing, sambil meminimumkan komponennya dengan mengurangkan separuh mereka.

Kaedah 2: Kaedah menyusun

Isihan menaik membantu mengesan sama ada setiap item tatasusunan boleh menjadikan dirinya sebagai nilai yang sepadan dalam senarai yang diisih. Jika tiada item yang memenuhi kriteria ini, output kami akan menghasilkan palsu namun, jika semua item lulus ujian ini, ia akan kembali benar.

Contoh

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

bool canBePermutation(std::vector<int>& arr) {
   std::sort(arr.begin(), arr.end());

   for (int i = 0; i < arr.size(); i++) {
      int expected = i + 1;
      while (arr[i] > 0 && arr[i] != expected)
         arr[i] /= 2;

      if (arr[i] != expected)
         return false;
   }
   
   return true;
}

int main() {
   std::vector<int> arr = {4, 2, 1, 3};
   
   if (canBePermutation(arr)) {
      std::cout << "The given array can be transformed into a permutation.";
   } else {
      std::cout << "The given array cannot be transformed into a permutation.";
   }
   
   return 0;
}

Output

The given array can be transformed into a permutation.

Arahan

Mengikut kaedah 2 (kaedah pengisihan), kami terlebih dahulu mengisih tatasusunan input asal dalam tertib menaik sebelum menyemak lebih lanjut rutin kod. Kod itu kemudian menjalankan pelbagai lelaran pada setiap elemen individu tatasusunan di atas sambil menyemak sama ada ia boleh dibahagikan dengan dua sehingga ia mencapai nilai yang ditentukan dan diandaikan yang ditetapkan berdasarkan kedudukannya dalam julat kedudukan nilai indeks yang baru diisih. Jika terdapat sebarang kes dalam lelaran sedemikian yang tidak memenuhi syarat utama yang dipratentukan ini, maka kod kami menghuraikan hasilnya sebagai "Salah", yang bermaksud bahawa tidak mungkin untuk menukar tatasusunan ini kepada susunan jujukan yang sepadan. Pada masa yang sama, sebaliknya, setiap elemen pematuhan menghasilkan hasil "benar", memberikan arah positif yang boleh dilaksanakan untuk matlamat penyusunan semula tatasusunan kami.

Kesimpulan

Dalam siaran ini, kami menyelidiki cabaran untuk mengesahkan sama ada tatasusunan yang diberikan boleh diubah menjadi pilih atur yang mengandungi nombor dalam julat 1 hingga N dengan mengurangkan separuh elemennya. Kami menyediakan pembaca garis besar, sintaks dan prosedur algoritma untuk menyelesaikan masalah ini dengan cekap. Selain itu, kami menyediakan dua pendekatan yang mungkin bersama-sama dengan contoh kod boleh laku C++ yang lengkap. Dengan menggunakan teknik berasaskan set atau strategi pengisihan yang diserlahkan dalam artikel ini, pembaca boleh menentukan mengikut kepuasannya sama ada mana-mana tatasusunan memenuhi semua syarat yang diperlukan untuk pengaturan undang-undang.

Atas ialah kandungan terperinci Semak sama ada tatasusunan yang diberikan boleh membentuk pilih atur daripada 1 hingga N dengan mengurangkan separuh unsur. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!