Cari jika Tatasusunan Boleh Diisih

3011. Cari jika Tatasusunan Boleh Diisih

Kesukaran: Sederhana

Topik: Tatasusunan, Manipulasi Bit, Isih

Anda diberi 0-diindeks tatasusunan positif nombor integer.

Dalam satu operasi, anda boleh menukar mana-mana dua bersebelahan elemen jika mereka mempunyai sama bilangan bit set¹. Anda dibenarkan melakukan operasi ini sebarang bilangan kali (termasuk sifar).

Kembalikan benar jika anda boleh mengisih tatasusunan, jika tidak, kembalikan palsu.

Contoh 1:

• Input: nombor = [8,4,2,30,15]
• Output: benar
• Penjelasan: Mari kita lihat perwakilan binari setiap elemen. Nombor 2, 4, dan 8 mempunyai satu set bit masing-masing dengan perwakilan binari "10", "100", dan "1000" masing-masing. Nombor 15 dan 30 mempunyai empat set bit setiap satu dengan perwakilan binari "1111" dan "11110". Kita boleh menyusun tatasusunan menggunakan 4 operasi:
  • Tukar nombor[0] dengan nombor[1]. Operasi ini sah kerana 8 dan 4 mempunyai satu set bit setiap satu. Tatasusunan menjadi [4,8,2,30,15].
  • Tukar nombor[1] dengan nombor[2]. Operasi ini sah kerana 8 dan 2 mempunyai satu set bit setiap satu. Tatasusunan menjadi [4,2,8,30,15].
  • Tukar nombor[0] dengan nombor[1]. Operasi ini sah kerana 4 dan 2 mempunyai satu set bit setiap satu. Tatasusunan menjadi [2,4,8,30,15].
  • Tukar nombor[3] dengan nombor[4]. Operasi ini sah kerana 30 dan 15 mempunyai empat set bit setiap satu. Tatasusunan menjadi [2,4,8,15,30].
  • Tatasusunan telah diisih, oleh itu kami kembali benar.
  • Perhatikan bahawa mungkin terdapat turutan operasi lain yang turut mengisih tatasusunan.

Contoh 2:

• Input: nombor = [1,2,3,4,5]
• Output: benar
• Penjelasan: Tatasusunan sudah diisih, oleh itu kami kembali benar.

Contoh 3:

• Input: nombor = [3,16,8,4,2]
• Output: palsu
• Penjelasan: Ia boleh ditunjukkan bahawa tidak mungkin untuk mengisih tatasusunan input menggunakan sebarang bilangan operasi.

Contoh 4:

• Input: nombor = [75,34,30]
• Output: palsu
• Penjelasan: Ia boleh ditunjukkan bahawa tidak mungkin untuk mengisih tatasusunan input menggunakan sebarang bilangan operasi.

Kekangan:

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 2⁸

Petunjuk:

1. Pisah tatasusunan kepada segmen. Setiap segmen mengandungi elemen berturut-turut dengan bilangan bit set yang sama.
2. Dari kiri ke kanan, elemen terbesar segmen sebelumnya harus lebih kecil daripada elemen terkecil segmen semasa.

Penyelesaian:

Kita perlu menentukan sama ada tatasusunan boleh diisih dengan hanya menukar elemen bersebelahan yang mempunyai bilangan bit set yang sama dalam perwakilan binarinya. Inilah rancangannya:

Langkah Penyelesaian:

1. Pemerhatian Utama: Operasi membenarkan kami menukar elemen bersebelahan hanya jika ia mempunyai bilangan bit set yang sama. Ini mengehadkan pertukaran merentas elemen dengan bilangan bit set yang berbeza.

2. Rancang:

   • Kumpulkan elemen mengikut bilangan set bit dalam perwakilan binarinya.
   • Isih setiap kumpulan secara individu, kerana dalam kumpulan, elemen boleh disusun semula melalui pertukaran.
   • Selepas mengisih setiap kumpulan, gabungkan kumpulan yang diisih kembali bersama.
   • Semak sama ada tatasusunan yang digabungkan ini diisih. Jika ya, maka menyusun tatasusunan menggunakan operasi yang dibenarkan adalah mungkin.

3. Langkah:

   • Kira bit set dalam setiap nombor dan nombor kumpulan dengan kiraan bit set yang sama.
   • Isih setiap kumpulan secara individu.
   • Bina semula tatasusunan daripada kumpulan yang diisih ini dan sahkan jika hasilnya diisih.

Mari kita laksanakan penyelesaian ini dalam PHP: 3011. Cari jika Tatasusunan Boleh Diisih

  
  
  Penjelasan:




Fungsi countSetBits: Mengira bilangan set bit dalam nombor menggunakan operasi bitwise.

Elemen Pengumpulan: bitGroups ialah tatasusunan bersekutu di mana setiap kekunci mewakili kiraan bit yang ditetapkan dan setiap nilai ialah tatasusunan nombor dengan bit set sebanyak itu.

Isih dan Bina Semula:


Kami mengulangi nombor kepada kumpulan elemen mengikut kiraan bit yang ditetapkan.
Kami mengisih setiap kumpulan secara berasingan.
Kami kemudian membina semula tatasusunan dengan memasukkan setiap elemen kumpulan yang diisih dalam susunan asalnya.
Akhir sekali, kami menyemak sama ada tatasusunan yang dibina semula diisih dalam susunan tidak menurun. Jika ya, kembalikan benar; jika tidak, pulangkan palsu.


Perbandingan Akhir: Bandingkan tatasusunan yang dibina semula dengan versi nombor yang diisih sepenuhnya. Jika ia sepadan, kembalikan benar; jika tidak, pulangkan palsu.



  
  
  Analisis Kerumitan




Kerumitan Masa: O(n log n) disebabkan oleh pengisihan dalam setiap kumpulan dan perbandingan terakhir.

Kerumitan Angkasa: O(n) untuk menyimpan kumpulan bit.


Penyelesaian ini memastikan bahawa kami hanya menukar elemen bersebelahan dengan kiraan bit set yang sama, mencapai susunan yang diisih jika boleh.

Pautan Kenalan
Jika anda mendapati siri ini membantu, sila pertimbangkan untuk memberi repositori bintang di GitHub atau berkongsi siaran pada rangkaian sosial kegemaran anda ?. Sokongan anda amat bermakna bagi saya!

Jika anda mahukan kandungan yang lebih berguna seperti ini, sila ikuti saya:


LinkedIn
GitHub








Set Bit Set bit merujuk kepada bit dalam perwakilan binari nombor yang mempunyai nilai 1. ↩





          

            
  

            
        
Atas ialah kandungan terperinci Cari jika Tatasusunan Boleh Diisih. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!