. Elemen Meliputi Julat Terkecil daripada Senarai K

632. Elemen Meliputi Julat Terkecil daripada K List

Kesukaran: Sukar

Topik: Tatasusunan, Jadual Cincang, Tamak, Tingkap Gelongsor, Isih, Timbunan (Baris Gilir Keutamaan)

Anda mempunyai k senarai integer yang diisih dalam tertib tidak menurun. Cari julat terkecil yang merangkumi sekurang-kurangnya satu nombor daripada setiap senarai k.

Kami mentakrifkan julat [a, b] adalah lebih kecil daripada julat [c, d] jika b - a < d - c atau a < c jika b - a == d - c.

Contoh 1:

• Input: nombor = [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]
• Output: [20,24]
• Penjelasan:
  • Senarai 1: [4, 10, 15, 24,26], 24 berada dalam julat [20,24].
  • Senarai 2: [0, 9, 12, 20], 20 berada dalam julat [20,24].
  • Senarai 3: [5, 18, 22, 30], 22 berada dalam julat [20,24].

Contoh 2:

• Input: nombor = [[1,2,3],[1,2,3],[1,2,3]]
• Output: [1,1]

Kekangan:

• bilangan panjang == k
• 1 <= k <= 3500
• 1 <= nums[i].panjang <= 50
• -10⁵ <= nums[i][j] <= 10⁵
• nums[i] diisih mengikut urutan tidak berkurang.

Penyelesaian:

Kita boleh menggunakan min-timbunan (atau baris gilir keutamaan) untuk menjejak elemen terkecil daripada setiap senarai sambil mengekalkan tetingkap gelongsor untuk mencari julat terkecil yang merangkumi sekurang-kurangnya satu elemen daripada setiap senarai.

Pendekatan

1. Min-Heap Initialization: Gunakan min-heap untuk menyimpan elemen semasa daripada setiap senarai k. Setiap entri timbunan akan menjadi tuple yang mengandungi nilai, indeks senarai asalnya dan indeks elemen dalam senarai itu.
2. Penjejakan Nilai Maks: Jejaki nilai maksimum dalam tetingkap semasa. Ini penting kerana julat ditentukan oleh perbezaan antara unsur terkecil (dari timbunan) dan maksimum semasa.
3. Lelaran Sehingga Tamat Senarai: Untuk setiap lelaran:
   • Ekstrak elemen minimum daripada timbunan.
   • Kemas kini julat jika julat semasa [min_value, max_value] adalah lebih kecil daripada julat terkecil yang direkodkan sebelum ini.
   • Beralih ke elemen seterusnya dalam senarai tempat elemen minimum diambil. Kemas kini nilai maks dan tambah elemen baharu pada timbunan.
4. Penamatan: Proses tamat apabila mana-mana senarai telah habis.

Mari laksanakan penyelesaian ini dalam PHP: 632. Julat Terkecil Elemen Meliputi daripada K List

  
  
  Penjelasan:




Permulaan Timbunan:


Timbunan awal mengandungi elemen pertama daripada setiap senarai. Kami juga menjejaki elemen maksimum antara elemen pertama.



Memproses Timbunan:


Ekstrak elemen minimum daripada timbunan, dan kemudian cuba lanjutkan julat dengan menambahkan elemen seterusnya daripada senarai yang sama (jika ada).
Selepas menambah elemen baharu pada timbunan, kemas kini maxValue jika elemen baharu lebih besar.
Kemas kini julat terkecil apabila perbezaan antara maxValue dan minValue lebih kecil daripada julat yang direkodkan sebelum ini.



Penamatan:


Gelung berhenti apabila mana-mana senarai kehabisan elemen, kerana kami tidak boleh memasukkan semua senarai dalam julat lagi.





  
  
  Analisis Kerumitan




Kerumitan Masa: O(n * log k), dengan n ialah jumlah bilangan elemen merentas semua senarai dan k ialah bilangan senarai. Kerumitan datang daripada memasukkan dan mengalih keluar elemen daripada timbunan.

Kerumitan Angkasa: O(k) untuk menyimpan elemen dalam timbunan.


Penyelesaian ini cekap mencari julat terkecil yang merangkumi sekurang-kurangnya satu nombor daripada setiap senarai yang disusun k.

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 . Elemen Meliputi Julat Terkecil daripada Senarai K. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!