Cari Skor Tatasusunan Selepas Menanda Semua Elemen

2593. Cari Skor Tatasusunan Selepas Menanda Semua Elemen

Kesukaran: Sederhana

Topik: Timbunan (Baris Gilir Keutamaan), Isih, Tatasusunan, Simulasi, Jadual Cincang, Set Tersusun, Peta Tersusun, Tamak, Timbunan Monotonic, Tingkap Gelongsor, Dua Penunjuk, Tindanan, Baris, Manipulasi Bit, Bahagi dan Takluk, Pengaturcaraan Dinamik, Senarai Berkait Berganda, Strim Data, Isih Radix, Penjejakan Belakang, Bitmask, Pokok, Reka Bentuk, Fungsi Cincang, Rentetan, Iterator, Isih Mengira, Senarai Terpaut

Anda diberi nombor tatasusunan yang terdiri daripada integer positif.

Bermula dengan skor = 0, gunakan algoritma berikut:

• Pilih integer terkecil bagi tatasusunan yang tidak ditanda. Jika seri, pilih yang mempunyai indeks terkecil.
• Tambahkan nilai integer yang dipilih untuk menjaringkan.
• Tandakan elemen yang dipilih dan dua elemen bersebelahannya jika wujud.
• Ulang sehingga semua elemen tatasusunan ditanda.

Kembalikan skor yang anda perolehi selepas menggunakan algoritma di atas.

Contoh 1:

• Input: nombor = [2,1,3,4,5,2]
• Output: 7
• Penjelasan: Kami menandakan elemen seperti berikut:
  • 1 ialah unsur terkecil tidak bertanda, jadi kami menandainya dan dua elemen bersebelahannya: [2,1,3,4,5,2].
  • 2 ialah unsur terkecil tidak bertanda, jadi kami menandainya dan elemen bersebelahan kirinya: [2,1,3,4,5,2].
  • 4 ialah satu-satunya elemen tidak bertanda yang tinggal, jadi kami menandakannya: [2,1,3,4,5,2].
  • Markah kami ialah 1 2 4 = 7.

Contoh 2:

• Input: nombor = [2,3,5,1,3,2]
• Output: 5
• Penjelasan: Kami menandakan elemen seperti berikut:
  • 1 ialah unsur terkecil tidak bertanda, jadi kami menandainya dan dua elemen bersebelahannya: [2,3,5,1,3,2].
  • 2 ialah elemen terkecil tidak bertanda, kerana terdapat dua daripadanya, kami memilih yang paling kiri, jadi kami menandai satu di indeks 0 dan elemen bersebelahan kanannya: [2,3,5,1,3, 2].
  • 2 ialah satu-satunya elemen tidak bertanda yang tinggal, jadi kami menandakannya: [2,3,5,1,3,2].
  • Markah kami ialah 1 2 2 = 5.

Kekangan:

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

Petunjuk:

1. Cuba simulasikan proses menanda unsur dan bersebelahannya.
2. Jika terdapat elemen yang telah ditanda, maka anda melangkaunya.

Penyelesaian:

Kami boleh mensimulasikan proses penandaan dengan cekap dengan menggunakan tatasusunan yang diisih atau baris gilir keutamaan untuk menjejaki elemen terkecil yang tidak ditanda. Jadi kita boleh menggunakan pendekatan berikut:

Pelan:

1. Penghuraian Input: Baca nombor tatasusunan dan mulakan pembolehubah untuk skor dan status penandaan.
2. Timbunan (Baris Gilir Keutamaan):
   • Gunakan timbunan min untuk mengekstrak elemen terkecil yang tidak bertanda dalam setiap langkah dengan cekap.
   • Masukkan setiap elemen ke dalam timbunan bersama dengan indeksnya (nilai, indeks) untuk mengurus ikatan berdasarkan indeks terkecil.
3. Elemen Penandaan:
   • Kekalkan tatasusunan bertanda untuk menjejaki sama ada elemen dan elemen bersebelahan dengannya ditanda.
   • Apabila memproses elemen daripada timbunan, langkau unsur itu jika ia sudah ditanda.
   • Tandakan elemen semasa dan dua elemen bersebelahannya (jika wujud).
   • Tambahkan nilai elemen semasa pada skor.
4. Ulang: Teruskan sehingga semua elemen ditanda.
5. Output: Kembalikan markah terkumpul.

Mari laksanakan penyelesaian ini dalam PHP: 2593. Cari Skor Tatasusunan Selepas Menanda Semua Elemen

  
  
  Penjelasan:




Pembinaan Timbunan:


Fungsi usort mengisih tatasusunan berdasarkan nilai dan mengikut indeks apabila nilai diikat.
Ini memastikan kami sentiasa memproses elemen terkecil tidak bertanda dengan indeks terkecil.



Logik Penandaan:


Untuk setiap elemen yang tidak bertanda, kami menandainya dan elemen bersebelahannya menggunakan tatasusunan yang ditanda.
Ini memastikan kami melangkau elemen yang ditanda sebelum ini dengan cekap.



Kerumitan Masa:


Mengisih timbunan: O(n log n)

Memproses timbunan: O(n)

Keseluruhan: O(n log n), yang cekap untuk kekangan yang diberikan.



Kerumitan Angkasa:


 Tatasusunan bertanda: O(n)

Timbunan: O(n)

Jumlah: O(n)





Penyelesaian ini memenuhi kekangan dan berfungsi dengan cekap untuk input yang besar.

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 Cari Skor Tatasusunan Selepas Menanda Semua Elemen. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!