Finden Sie fehlende Beobachtungen

2028. Finden Sie fehlende Beobachtungen

Schwierigkeit:Mittel

Themen:Array, Mathematik, Simulation

Sie haben Beobachtungen von n + m 6-seitigen Würfelwürfen, wobei jede Seite von 1 bis 6 nummeriert ist. n der Beobachtungen sind verloren gegangen und Sie haben nur die Beobachtungen von m Würfelwürfen. Glücklicherweise haben Sie auch den Durchschnittswert der n + m Rollen berechnet.

Sie erhalten ein ganzzahliges Array rolls der Länge m, wobei rolls[i] der Wert der i^ten Beobachtung ist. Sie erhalten außerdem die beiden ganzen Zahlen Mittelwert und n.

Gib ein Array der Länge n zurück, das die fehlenden Beobachtungen enthält, sodass der Durchschnittswert der n + m Würfe genau der Mittelwert ist. Wenn es mehrere gültige Antworten gibt, geben Sie eine davon zurück. Wenn kein solches Array vorhanden ist, geben Sie ein leeres Array zurück.

Der Durchschnittswert einer Menge von k Zahlen ist die Summe der Zahlen dividiert durch k.

Beachten Sie, dass der Mittelwert eine ganze Zahl ist, daher sollte die Summe der n + mrollen durch n + m teilbar sein.

Beispiel 1:

• Eingabe:Rollen = [3,2,4,3], Mittelwert = 4, n = 2
• Ausgabe: [6,6]
• Erklärung:Der Mittelwert aller n + m Würfe ist (3 + 2 + 4 + 3 + 6 + 6) / 6 = 4.

Beispiel 2:

• Eingabe:Rollen = [1,5,6], Mittelwert = 3, n = 4
• Ausgabe: [2,3,2,2]
• Erklärung:Der Mittelwert aller n + m Würfe ist (1 + 5 + 6 + 2 + 3 + 2 + 2) / 7 = 3.

Beispiel 3:

• Eingabe:Rollen = [1,2,3,4], Mittelwert = 6, n = 4
• Ausgabe: []
• Erklärung:Es ist unmöglich, dass der Mittelwert 6 beträgt, egal wie hoch die 4 fehlenden Würfe sind.

Einschränkungen:

• m == Rollenlänge
• 1 <= n, m <= 10⁵
• 1 <= rollt[i], Mittelwert <= 6

Hinweis:

1. Wie hoch sollte die Summe der n Würfe sein?
2. Könnten Sie ein Array der Größe n generieren, sodass jedes Element zwischen 1 und 6 liegt?

Lösung:

Wir müssen eine Reihe fehlender Würfe bestimmen, sodass der Durchschnitt aller n + m Würfelwürfe genau dem Mittelwert entspricht. Hier ist die Schritt-für-Schritt-Aufschlüsselung der Lösung:

Schritte zur Vorgehensweise:

1. Berechnen Sie die Gesamtsumme für n + m Rollen:
   Da der Durchschnittswert von n + m Rollen der Mittelwert ist, sollte die Gesamtsumme aller Rollen total_sum = (n + m) * Mittelwert sein.

2. Bestimmen Sie die fehlende Summe:
   Die Summe der m Rollen ist bereits bekannt. Somit sollte die Summe der fehlenden n Rollen sein:
   

   missing_sum = total_sum - ∑(rolls)

wobei ∑(Rolls) die Summe der Elemente im Rolls-Array ist.

1. Prüfung auf Machbarkeit: Bei jedem Wurf handelt es sich um einen 6-seitigen Würfel, daher müssen die fehlenden Werte zwischen 1 und 6 (einschließlich) liegen. Daher muss die Summe der fehlenden n Würfe zwischen:

   min_sum = n X 1 = n

und

   max_sum = n X 6 = 6n

Wenn die fehlende_Summe außerhalb dieses Bereichs liegt, ist es unmöglich, gültige fehlende Beobachtungen zu bilden, und wir sollten ein leeres Array zurückgeben.

1. Verteilen Sie die fehlende Summe: Wenn „missing_sum“ gültig ist, verteilen wir es auf die n Rollen, indem wir zunächst jedes Element mit 1 (dem minimal möglichen Wert) füllen. Dann erhöhen wir die Elemente von 1 auf 6, bis wir die erforderliche fehlende Summe erreichen.

Lassen Sie uns diese Lösung in PHP implementieren: 2028. Finden Sie fehlende Beobachtungen

  
  
  Erläuterung:




Eingabe:


Rollen = [3, 2, 4, 3]
Mittelwert = 4
n = 2



Schritte:


Die Gesamtzahl der Rollen beträgt n + m = 6.
Die benötigte Gesamtsumme beträgt 6 * 4 = 24.
Die Summe der gegebenen Würfe beträgt 3 + 2 + 4 + 3 = 12.
Die erforderliche Summe für die fehlenden Rollen beträgt 24 - 12 = 12.




Wir brauchen zwei fehlende Würfe, die zusammen 12 ergeben, und die einzige Möglichkeit ist [6, 6].



Ergebnis:


Beispiel 1: Die Ausgabe ist [6, 6].
Beispiel 2: Die Ausgabe ist [2, 3, 2, 2].
Zum Beispiel 3: Keine gültige Lösung, daher ist die Ausgabe [].





  
  
  Zeitkomplexität:



Das Berechnen der Summe der Würfe erfordert O(m) und das Verteilen der fehlenden_Summe erfordert O(n). Daher beträgt die Gesamtzeitkomplexität O(n + m), was für die Eingabebeschränkungen effizient ist.


Diese Lösung stellt sicher, dass wir entweder gültige fehlende Rollen finden oder ein leeres Array zurückgeben, wenn keine Lösung existiert.

Kontaktlinks
如果您發現本系列有幫助，請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！ 

如果您想要更多類似的有用內容，請隨時關注我：


領英
GitHub



          

            
        
Das obige ist der detaillierte Inhalt vonFinden Sie fehlende Beobachtungen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!