Item Paling Cantik untuk Setiap Pertanyaan

2070. Item Paling Cantik untuk Setiap Pertanyaan

Kesukaran: Sederhana

Topik: Tatasusunan, Carian Binari, Isih

Anda diberikan item tatasusunan integer 2D di mana item[i] = [harga_i, kecantikan_i] menandakan harga dan kecantikan satu item masing-masing.

Anda juga diberikan pertanyaan tatasusunan integer 0-diindeks. Untuk setiap pertanyaan[j], anda ingin menentukan kecantikan maksimum item yang harganya kurang daripada atau sama dengan pertanyaan[j]. Jika tiada item sedemikian wujud, maka jawapan kepada pertanyaan ini ialah 0.

Kembalikan jawapan tatasusunan yang sama panjang dengan pertanyaan dengan jawapan[j] ialah jawapan kepada pertanyaan ke-j.

Contoh 1:

• Input: item = [[1,2],[3,2],[2,4],[5,6],[3,5]], pertanyaan = [1,2,3 ,4,5,6]
• Output: [2,4,5,5,6,6]
• Penjelasan:
  • Untuk pertanyaan[0]=1, [1,2] ialah satu-satunya item yang mempunyai harga <= 1. Oleh itu, jawapan untuk pertanyaan ini ialah 2.
  • Untuk pertanyaan[1]=2, item yang boleh dipertimbangkan ialah [1,2] dan [2,4].
  • Kecantikan maksimum antaranya ialah 4.
  • Untuk pertanyaan[2]=3 dan pertanyaan[3]=4, item yang boleh dipertimbangkan ialah [1,2], [3,2], [2,4] dan [3,5].
  • Kecantikan maksimum antaranya ialah 5.
  • Untuk pertanyaan[4]=5 dan pertanyaan[5]=6, semua item boleh dipertimbangkan.
  • Oleh itu, jawapan bagi mereka ialah keindahan maksimum semua item, iaitu, 6.

Contoh 2:

• Input: item = [[1,2],[1,2],[1,3],[1,4]], pertanyaan = [1]
• Output: [4]
• Penjelasan: Harga setiap item adalah sama dengan 1, jadi kami memilih item dengan kecantikan maksimum 4.
  • Perhatikan bahawa berbilang item boleh mempunyai harga dan/atau kecantikan yang sama.

Contoh 3:

• Input: item = [[10,1000]], pertanyaan = [5]
• Output: [0]
• Penjelasan: Tiada item yang mempunyai harga kurang daripada atau sama dengan 5, jadi tiada item boleh dipilih.
  • Oleh itu, jawapan kepada pertanyaan ialah 0.

Kekangan:

• 1 <= item.length, queries.length <= 10⁵
• item[i].panjang == 2
• 1 <= harga_i, kecantikan_i, pertanyaan[j] <= 10⁹

Petunjuk:

1. Bolehkah kami memproses pertanyaan dalam susunan pintar untuk mengelak daripada menyemak item yang sama berulang kali?
2. Bagaimanakah kita boleh menggunakan jawapan kepada pertanyaan untuk pertanyaan lain?

Penyelesaian:

Kita boleh menggunakan teknik pengisihan dan carian binari. Inilah rancangannya:

Pendekatan

1. Isih Item mengikut Harga:

   • Pertama, susun item mengikut harganya. Dengan cara ini, semasa kami mengulangi item, kami boleh menjejaki keindahan maksimum yang dilihat setakat ini untuk item sehingga mana-mana harga tertentu.

2. Isih Pertanyaan dengan Indeks Asalnya:

   • Buat tatasusunan pertanyaan yang digandingkan dengan indeks asalnya, kemudian susun tatasusunan ini mengikut nilai pertanyaan.
   • Isih membantu kerana kami boleh memproses pertanyaan dalam susunan harga yang semakin meningkat dan mengelakkan pengiraan semula nilai kecantikan untuk harga yang lebih rendah berulang kali.

3. Lelar melalui Item dan Pertanyaan Serentak:

   • Menggunakan dua penunjuk, proses setiap pertanyaan:
     • Untuk setiap pertanyaan, gerakkan penunjuk melalui item dengan harga kurang daripada atau sama dengan harga pertanyaan.
     • Jejaki keindahan maksimum semasa anda meneliti item ini dan gunakan nilai ini untuk menjawab pertanyaan semasa.
     • Ini mengelakkan menyemak item berulang kali untuk berbilang pertanyaan.

4. Hasil Simpan dan Pemulangan:

   • Setelah diproses, simpan hasil kecantikan maksimum untuk setiap pertanyaan berdasarkan indeks asal untuk mengekalkan pesanan.
   • Kembalikan tatasusunan jawapan.

Mari laksanakan penyelesaian ini dalam PHP: 2070. Item Paling Cantik untuk Setiap Pertanyaan

  
  
  Penjelasan:




Mengisih item dan pertanyaan: Ini membolehkan pemprosesan yang cekap tanpa pengiraan berlebihan.

Teknik dua mata: Memindahkan item sekali sahaja untuk setiap pertanyaan mengelakkan pengiraan yang berlebihan.

Jejaki maxBeauty: Kami mengemas kini maxBeauty secara berperingkat, membenarkan setiap pertanyaan mengakses keindahan tertinggi yang dilihat setakat ini.



  
  
  Kerumitan




Kerumitan Masa: O(n log n m log m) untuk mengisih item dan pertanyaan, dan O(n m) untuk pemprosesan, dengan n ialah panjang item dan m ialah panjang pertanyaan.

Kerumitan Angkasa: O(m) untuk menyimpan hasil.


Penyelesaian ini cekap dan memenuhi kekangan masalah.

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 Item Paling Cantik untuk Setiap Pertanyaan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!