Trouver les observations manquantes

2028. Trouver les observations manquantes

Difficulté :Moyen

Sujets :Tableau, Mathématiques, Simulation

Vous avez des observations de n + m lancements de dés à 6 faces avec chaque face numérotée de 1 à 6. n des observations ont disparu, et vous n'avez que les observations de m lancers. Heureusement, vous avez également calculé la valeur moyenne des n+m lancers.

Vous recevez un tableau d'entiers rolls de longueur m où rolls[i] est la valeur de la i^ième observation. Vous recevez également les deux entiers moyenne et n.

Renvoyer un tableau de longueur n contenant les observations manquantes telles que la valeur moyenne des n + m lancers soit exactement moyenne. S'il y a plusieurs réponses valides, renvoyez-en une. Si aucun tableau de ce type n'existe, renvoyez un tableau vide.

La valeur moyenne d'un ensemble de k nombres est la somme des nombres divisée par k.

Notez que la moyenne est un nombre entier, donc la somme des n + mrolls doit être divisible par n + m.

Exemple 1 :

• Entrée : rolls = [3,2,4,3], moyenne = 4, n = 2
• Sortie : [6,6]
• Explication : La moyenne de tous les n + m lancers est (3 + 2 + 4 + 3 + 6 + 6) / 6 = 4.

Exemple 2 :

• Entrée : rolls = [1,5,6], moyenne = 3, n = 4
• Sortie : [2,3,2,2]
• Explication : La moyenne de tous les n + m lancers est (1 + 5 + 6 + 2 + 3 + 2 + 2) / 7 = 3.

Exemple 3 :

• Entrée : rolls = [1,2,3,4], moyenne = 6, n = 4
• Sortie : []
• Explication : Il est impossible que la moyenne soit de 6 quels que soient les 4 lancers manquants.

Contraintes :

• m == rouleaux.longueur
• 1 <= n, m <= 10⁵
• 1 <= rouleaux[i], moyenne <= 6

Indice :

1. Quelle devrait être la somme des n lancers ?
2. Pourriez-vous générer un tableau de taille n tel que chaque élément soit compris entre 1 et 6 ?

Solution :

Nous devons déterminer un tableau de lancers manquants tel que la moyenne de tous les n + m lancers de dés soit exactement égale à la moyenne. Voici le détail étape par étape de la solution :

Étapes à suivre :

1. Calculez la somme totale pour n + m rouleaux :
   Étant donné que la valeur moyenne de n + m lancers est moyenne, la somme totale de tous les lancers devrait être total_sum = (n + m) * moyenne.

2. Déterminez la somme manquante :
   La somme des m lancers est déjà connue. Ainsi, la somme des n lancers manquants devrait être :
   

   missing_sum = total_sum - ∑(rolls)

où ∑(rolls) est la somme des éléments du tableau rolls.

1. Vérifier la faisabilité : Chaque lancer est un dé à 6 faces, les valeurs manquantes doivent donc être comprises entre 1 et 6 (inclus). La somme des n lancers manquants doit donc être comprise entre :

   min_sum = n X 1 = n

et

   max_sum = n X 6 = 6n

Si la somme_manquante est en dehors de cette plage, il est impossible de former des observations manquantes valides et nous devrions renvoyer un tableau vide.

1. Distribuez la somme manquante : Si la somme manquante est valide, nous la répartissons sur les n rouleaux en remplissant initialement chaque élément avec 1 (la valeur minimale possible). Ensuite, nous incrémentons les éléments de 1 à 6 jusqu'à atteindre la somme manquante requise.

Implémentons cette solution en PHP : 2028. Trouver les observations manquantes

  
  
  Explication:




Entrée :


rouleaux = [3, 2, 4, 3]
moyenne = 4
n=2



Étapes :


Le nombre total de rouleaux est n + m = 6.
La somme totale nécessaire est de 6 * 4 = 24.
La somme des lancers donnés est 3 + 2 + 4 + 3 = 12.
La somme requise pour les rouleaux manquants est de 24 - 12 = 12.




Nous avons besoin de deux lancers manquants qui totalisent 12, et la seule possibilité est [6, 6].



Résultat :


Par exemple 1 : la sortie est [6, 6].
Par exemple 2 : la sortie est [2, 3, 2, 2].
Par exemple 3 : aucune solution valide, le résultat est donc [].





  
  
  Complexité temporelle :



Le calcul de la somme des lancers prend O(m), et la distribution de la somme_manquante prend O(n). Par conséquent, la complexité temporelle globale est O(n + m), ce qui est efficace pour les contraintes d'entrée.


Cette solution garantit que nous trouvons soit des rouleaux manquants valides, soit que nous renvoyons un tableau vide lorsqu'aucune solution n'existe.

Liens de contact
Si vous avez trouvé cette série utile, pensez à donner une étoile au référentiel sur GitHub ou à partager la publication sur vos réseaux sociaux préférés ?. Votre soutien signifierait beaucoup pour moi !

Si vous souhaitez du contenu plus utile comme celui-ci, n'hésitez pas à me suivre :


LinkedIn
GitHub



          

            
        
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!