Cari Pemerhatian yang Hilang

2028. Cari Pemerhatian yang Hilang

Kesukaran: Sederhana

Topik: Tatasusunan, Matematik, Simulasi

Anda mempunyai pemerhatian n + m 6 belah gulung dadu dengan setiap muka bernombor dari 1 hingga 6. n daripada pemerhatian telah hilang, dan anda hanya mempunyai pemerhatian m gulung. Nasib baik, anda juga telah mengira nilai purata bagi n + m gulung.

Anda diberi gulung tatasusunan integer dengan panjang m di mana gulungan[i] ialah nilai pemerhatian i^th. Anda juga diberi dua integer min dan n.

Kembalikan susunan panjang n yang mengandungi pemerhatian yang hilang supaya nilai purata bagi n + m gulung adalah betul-betul min. Jika terdapat berbilang jawapan yang sah, kembalikan mana-mana daripadanya. Jika tiada tatasusunan sedemikian wujud, kembalikan tatasusunan kosong.

nilai purata set nombor k ialah hasil tambah nombor dibahagikan dengan k.

Nota bahawa min ialah integer, jadi hasil tambah n + mroll hendaklah dibahagi dengan n + m.

Contoh 1:

• Input: gulung = [3,2,4,3], min = 4, n = 2
• Output: [6,6]
• Penjelasan: Min bagi semua gulungan n + m ialah (3 + 2 + 4 + 3 + 6 + 6) / 6 = 4.

Contoh 2:

• Input: gulung = [1,5,6], min = 3, n = 4
• Output: [2,3,2,2]
• Penjelasan: Min bagi semua gulungan n + m ialah (1 + 5 + 6 + 2 + 3 + 2 + 2) / 7 = 3.

Contoh 3:

• Input: gulung = [1,2,3,4], min = 6, n = 4
• Output: []
• Penjelasan: Adalah mustahil untuk min menjadi 6 tidak kira apa 4 gulungan yang hilang itu.

Kekangan:

• m == gulungan.panjang
• 1 <= n, m <= 10⁵
• 1 <= gulung[i], min <= 6

Petunjuk:

1. Apakah jumlah n gulung yang sepatutnya?
2. Bolehkah anda menjana tatasusunan saiz n supaya setiap elemen adalah antara 1 dan 6?

Penyelesaian:

Kita perlu menentukan tatasusunan gulungan yang hilang supaya purata semua n + m gulungan dadu adalah sama dengan min. Berikut ialah pecahan langkah demi langkah penyelesaian:

Langkah-langkah untuk Mendekati:

1. Kira jumlah keseluruhan bagi n + m gulung:
   Memandangkan nilai purata bagi n + m gulung ialah min, jumlah keseluruhan semua gulung hendaklah jumlah_jumlah = (n + m) * min.

2. Tentukan jumlah yang hilang:
   Jumlah bagi m gulung sudah diketahui. Oleh itu, jumlah n gulung yang hilang hendaklah:
   

   missing_sum = total_sum - ∑(rolls)

di mana ∑(gulungan) ialah jumlah elemen dalam tatasusunan gulung.

1. Semak kebolehlaksanaan: Setiap gulungan ialah dadu 6 sisi, jadi nilai yang hilang mestilah antara 1 dan 6 (termasuk). Oleh itu, jumlah n gulung yang hilang mestilah antara:

   min_sum = n X 1 = n

dan

   max_sum = n X 6 = 6n

Jika missing_sum berada di luar julat ini, adalah mustahil untuk membentuk pemerhatian hilang yang sah dan kami harus mengembalikan tatasusunan kosong.

1. Agihkan jumlah yang hilang: Jika missing_sum adalah sah, kami mengedarkannya merentasi n gulung dengan mengisi setiap elemen dengan 1 pada mulanya (nilai kemungkinan minimum). Kemudian, kami menambah elemen daripada 1 kepada 6 sehingga kami mencapai jumlah_missing yang diperlukan.

Mari laksanakan penyelesaian ini dalam PHP: 2028. Cari Pemerhatian yang Hilang

  
  
  Penjelasan:




Input:


gulungan = [3, 2, 4, 3]
min = 4
n = 2



Langkah:


Jumlah bilangan gulungan ialah n + m = 6.
Jumlah jumlah yang diperlukan ialah 6 * 4 = 24.
Jumlah gulungan yang diberikan ialah 3 + 2 + 4 + 3 = 12.
Jumlah yang diperlukan untuk gulungan yang hilang ialah 24 - 12 = 12.




Kami memerlukan dua gulungan yang hilang yang berjumlah 12, dan satu-satunya kemungkinan ialah [6, 6].



Keputusan:


Contoh 1: Outputnya ialah [6, 6].
Contoh 2: Output ialah [2, 3, 2, 2].
Contoh 3: Tiada penyelesaian yang sah, jadi outputnya ialah [].





  
  
  Kerumitan Masa:



Mengira jumlah gulung mengambil O(m), dan mengagihkan jumlah_yang hilang mengambil O(n). Oleh itu, kerumitan masa keseluruhan ialah O(n + m), yang cekap untuk kekangan input.


Penyelesaian ini memastikan bahawa kami sama ada mencari gulungan hilang yang sah atau mengembalikan tatasusunan kosong apabila tiada penyelesaian wujud.

Pautan Kenalan
このシリーズが役立つと思われた場合は、GitHub で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:


LinkedIn
GitHub



          

            
        
Atas ialah kandungan terperinci Cari Pemerhatian yang Hilang. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!