2948. Jadikan Susunan Terkecil Secara Leksikografi dengan Bertukar Elemen

Kesukaran: Sederhana

Topik: Tatasusunan, Carian Kesatuan, Isih

Anda diberi 0-diindeks tatasusunan positif nombor integer dan had integer positif.

Dalam satu operasi, anda boleh memilih mana-mana dua indeks i dan j dan menukar nombor[i] dan nombor[j] jika |nums[i] - nums[j]| <= had.

Kembalikan tatasusunan terkecil dari segi leksikografi yang boleh diperolehi dengan melakukan operasi beberapa kali.

Suatu tatasusunan a secara leksikografi lebih kecil daripada tatasusunan b jika dalam kedudukan pertama di mana a dan b berbeza, tatasusunan a mempunyai unsur yang kurang daripada unsur yang sepadan dalam b. Sebagai contoh, tatasusunan [2,10,3] secara leksikografik lebih kecil daripada tatasusunan [10,2,3] kerana ia berbeza pada indeks 0 dan 2 < 10.

Contoh 1:

• Input: nombor = [1,5,3,9,8], had = 2
• Output: [1,3,5,8,9]
• Penjelasan: Sapukan operasi 2 kali:
  • Tukar nombor[1] dengan nombor[2]. Tatasusunan menjadi [1,3,5,9,8]
  • Tukar nombor[3] dengan nombor[4]. Tatasusunan menjadi [1,3,5,8,9]
  • Kami tidak boleh mendapatkan tatasusunan leksikografi yang lebih kecil dengan menggunakan sebarang operasi lagi.
  • Perhatikan bahawa mungkin untuk mendapatkan hasil yang sama dengan melakukan operasi yang berbeza.

Contoh 2:

• Input: nombor = [1,7,6,18,2,1], had = 3
• Output: [1,6,7,18,1,2]
• Penjelasan: Sapukan operasi 3 kali:
  • Tukar nombor[1] dengan nombor[2]. Tatasusunan menjadi [1,6,7,18,2,1]
  • Tukar nombor[0] dengan nombor[4]. Tatasusunan menjadi [2,6,7,18,1,1]
  • Tukar nombor[0] dengan nombor[5]. Tatasusunan menjadi [1,6,7,18,1,2]
  • Kami tidak boleh mendapatkan tatasusunan leksikografi yang lebih kecil dengan menggunakan sebarang operasi lagi.

Contoh 3:

• Input: nombor = [1,7,28,19,10], had = 3
• Output: [1,7,28,19,10]
• Penjelasan: [1,7,28,19,10] ialah tatasusunan terkecil dari segi leksikografi yang boleh kita perolehi kerana kita tidak boleh menggunakan operasi pada mana-mana dua indeks.

Contoh 4:

• Input: nombor = [1,60,34,84,62,56,39,76,49,38], had = 4
• Output: [1,56,34,84,60,62,38,76,49,39]

Kekangan:

• 1 <= nums.length <= 10⁵
• 1 <= nums[i] <= 10⁹
• 1 <= had <= 10⁹

Petunjuk:

1. Bina graf maya di mana semua elemen dalam nombor adalah nod dan pasangan yang memenuhi syarat mempunyai kelebihan di antara mereka.
2. Daripada membina semua tepi, kami hanya mengambil berat tentang komponen yang disambungkan.
3. Bolehkah kita menggunakan DSU?
4. Isih nombor. Sekarang kita hanya perlu mempertimbangkan jika elemen berturut-turut mempunyai kelebihan untuk memeriksa sama ada ia tergolong dalam komponen yang disambungkan yang sama. Oleh itu, semua komponen yang disambungkan menjadi senarai elemen berturut-turut kedudukan selepas diisih.
5. Untuk setiap indeks nombor daripada 0 kepada nums.length - 1 kita boleh menukarnya kepada nilai minimum semasa yang kita ada dalam komponen yang disambungkan dan mengalih keluar nilai itu daripada komponen yang disambungkan.

Penyelesaian:

Masalahnya meminta kami mencari tatasusunan terkecil dari segi leksikografi dengan menukar elemen tatasusunan, tertakluk pada syarat. Khususnya, kita hanya boleh menukar dua elemen nums[i] dan nums[j] jika perbezaan mutlak antara mereka (|nums[i] - nums[j]|) adalah kurang daripada atau sama dengan had tertentu.

Perkara Penting

1. Turutan Leksikografi: Tatasusunan a secara leksikografi lebih kecil daripada b jika pada indeks berbeza yang pertama, a[i] < b[i].
2. Syarat Pertukaran: Pertukaran hanya dibenarkan jika perbezaan antara nombor yang ditukar ialah had ≤.
3. Pengumpulan Cekap: Dengan menggunakan Disjoint Set Union (DSU) atau teknik pengisihan, kita boleh mengumpulkan elemen yang disambungkan dengan swap yang sah.
4. Susunan Optimum: Untuk setiap kumpulan, susun indeks dan nilai untuk mencapai susunan terkecil.

Pendekatan

1. Bina Kumpulan: Anggap tatasusunan sebagai graf maya, di mana swap yang sah menentukan tepi. Gunakan pengisihan untuk mengenal pasti kumpulan yang disambungkan atau DSU untuk mengumpulkan indeks dengan cekap.
2. Isih Kumpulan: Dalam setiap kumpulan indeks yang disambungkan, susun semula elemen dalam susunan leksikografi.
3. Pembinaan Output: Letakkan nilai yang diisih kembali ke kedudukan masing-masing.

Rancang

1. Ekstrak pasangan (nilai, indeks) dan isikannya mengikut nilai untuk membolehkan pengesanan kumpulan yang cekap.
2. Lelar melalui nilai yang diisih untuk membentuk kumpulan indeks yang disambungkan berdasarkan keadaan had.
3. Untuk setiap kumpulan:
   • Isih indeks dan nilai secara bebas.
   • Tetapkan semula nilai kepada kedudukan asalnya dalam susunan leksikografik.
4. Kembalikan tatasusunan yang diubah suai.

Mari laksanakan penyelesaian ini dalam PHP: 2948. Jadikan Susunan Terkecil Secara Leksikografi dengan Bertukar Elemen

  
  
  Penjelasan:




Mengekstrak dan Mengisih (getNumAndIndexes):

Gabungkan nilai dan indeks kepada pasangan untuk rujukan mudah.
Isih pasangan mengikut nilai untuk membolehkan pengelompokan komponen bersambung yang cekap.



Logik Pengumpulan:


Lintas pasangan yang diisih. Jika perbezaan antara nilai berturut-turut ialah ≤ had, tambahkannya pada kumpulan yang sama; jika tidak, mulakan kumpulan baharu.



Isih dan Penugasan Semula:


Untuk setiap kumpulan:


Ekstrak indeks dan nilai.
Isih kedua-dua senarai untuk memastikan nilai terkecil diletakkan dalam indeks terkecil.
Tetapkan semula nilai yang diisih ke kedudukan masing-masing dalam tatasusunan jawapan.





Pembinaan Keputusan:


Selepas memproses semua kumpulan, kembalikan tatasusunan yang dikemas kini.





  
  
  Contoh Panduan



  
  
  Contoh 1


Input: nombor = [1,5,3,9,8], had = 2



Ekstrak dan Isih:


Pasangan: [(1, 0), (5, 1), (3, 2), (9, 3), (8, 4)]

Pasangan Diisih: [(1, 0), (3, 2), (5, 1), (8, 4), (9, 3)]




Pengumpulan:


Kumpulan 1: [(1, 0)]

Kumpulan 2: [(3, 2), (5, 1)]

Kumpulan 3: [(8, 4), (9, 3)]




Isih Kumpulan:


Kumpulan 1: Tiada perubahan ([1])
Kumpulan 2: Nilai = [3, 5], Indeks = [1, 2] → Keputusan: [1, 3, 5]

Kumpulan 3: Nilai = [8, 9], Indeks = [3, 4] → Keputusan: [8, 9]



Keputusan Akhir: [1, 3, 5, 8, 9]



  
  
  Kerumitan Masa




Isih: Mengisih tatasusunan nombor memerlukan O(n log n).

Pengumpulan: Traversal linear melalui tatasusunan yang diisih mengambil masa O(n).

Isih Kumpulan: Isih indeks dan nilai untuk setiap kumpulan mengambil masa O(k log k), di mana k ialah saiz kumpulan. Dijumlahkan ke atas semua kumpulan, ini ialah O(n log n).


Kerumitan Masa Keseluruhan: O(n log n)


  
  
  Output untuk Contoh



  
  
  Contoh 2


Input: nombor = [1,7,6,18,2,1], had = 3


Output: [1,6,7,18,1,2]


  
  
  Contoh 3


Input: nombor = [1,7,28,19,10], had = 3


Output: [1,7,28,19,10]

Pendekatan ini cekap menangani masalah dengan menggunakan pengisihan untuk mengenal pasti komponen yang disambungkan dan menyusun semula nilai dalam setiap komponen untuk mencapai tatasusunan terkecil dari segi leksikografi. Dengan memanfaatkan pengisihan dan pemprosesan kumpulan, kami memastikan penyelesaian yang optimum dengan kerumitan O(n log n).

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



          

            
  

            
        
Atas ialah kandungan terperinci Jadikan Susunan Terkecil Secara Leksikografi dengan Bertukar Elemen. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!