Nombre maximum d'entiers à choisir dans une plage I

2554. Nombre maximum d'entiers à choisir dans une plage I

Difficulté :Moyen

Sujets : Tableau, table de hachage, recherche binaire, gourmand, tri

Vous recevez un tableau d'entiers interdits et deux entiers n et maxSum. Vous choisissez un certain nombre d'entiers en suivant les règles ci-dessous :

• Les entiers choisis doivent être compris entre [1, n].
• Chaque entier peut être choisi au maximum une fois.
• Les entiers choisis ne doivent pas être dans le tableau banni.
• La somme des entiers choisis ne doit pas dépasser maxSum.

Renvoyer le nombre maximum d'entiers que vous pouvez choisir en suivant les règles mentionnées.

Exemple 1 :

• Entrée : interdit = [1,6,5], n = 5, maxSum = 6
• Sortie : 2
• Explication : Vous pouvez choisir les entiers 2 et 4.
  • 2 et 4 sont de la plage [1, 5], les deux n'apparaissent pas dans les interdits, et leur somme est 6, qui n'a pas dépassé maxSum.

Exemple 2 :

• Entrée : interdit = [1,2,3,4,5,6,7], n = 8, maxSum = 1
• Sortie : 0
• Explication : Vous ne pouvez choisir aucun nombre entier en suivant les conditions mentionnées.

Exemple 3 :

• Entrée : interdit = [11], n = 7, maxSum = 50
• Sortie :7
• Explication : Vous pouvez choisir les entiers 1, 2, 3, 4, 5, 6 et 7.
  • Ils sont de la plage [1, 7], tous n'apparaissent pas dans les bannis, et leur somme est de 28, ce qui n'a pas dépassé maxSum.

Contraintes :

• 1 4
• 1 4
• 1 9

Indice :

1. Conservez les nombres interdits inférieurs à n dans un ensemble.
2. Faites une boucle sur les nombres de 1 à n et si le numéro n'est pas interdit, utilisez-le.
3. Continuez à ajouter des nombres tant qu'ils ne sont pas interdits et que leur somme est inférieure à k.

Solution :

Nous pouvons utiliser une approche gourmande où nous parcourons les nombres de 1 à n, en sautant les nombres interdits, et en continuant à ajouter les nombres valides (ceux qui ne figurent pas dans le tableau interdit) à une somme courante jusqu'à ce que nous atteignions la somme maximale.

Voici la solution étape par étape :

Mesures:

1. Convertir un tableau interdit en un ensemble pour des recherches rapides : L'utilisation de array_flip() peut convertir le tableau interdit en un ensemble pour des recherches de complexité en temps moyen O(1).
2. Itérer de 1 à n : Vérifiez chaque numéro, s'il ne fait pas partie de l'ensemble interdit et si son ajout ne dépasse pas maxSum, ajoutez-le à la somme et augmentez le nombre.
3. Arrêtez une fois que l'ajout du nombre suivant dépasse maxSum : Puisque l'objectif est de maximiser le nombre d'entiers choisis sans dépasser la somme, cette approche gourmande garantit que nous prenons en premier les plus petits nombres disponibles.

Approche:

1. Exclure les numéros interdits : Nous garderons une trace des numéros interdits dans un ensemble (ou un tableau associatif) pour des recherches rapides.
2. Sélection gourmande : Commencez à sélectionner les nombres de 1 à n par ordre croissant, car cela nous permettra de maximiser le nombre d'entiers sélectionnés. Chaque fois que nous sélectionnons un nombre, nous l'ajouterons à la somme et vérifierons s'il dépasse maxSum. Si c'est le cas, arrêtez.
3. Considérations d'efficacité : Puisque nous parcourons des nombres de 1 à n et vérifions si chacun est dans l'ensemble interdit (ce qui peut être fait en temps constant), l'approche s'exécute en temps linéaire par rapport à n et au taille de la liste des bannis.

Implémentons cette solution en PHP : 2554. Nombre maximum d'entiers à choisir dans une plage I

<?php /**
 * @param Integer[] $banned
 * @param Integer $n
 * @param Integer $maxSum
 * @return Integer
 */
function maxCount($banned, $n, $maxSum) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo maxCount([1, 6, 5], 5, 6);  // Output: 2
echo "\n";
echo maxCount([1, 2, 3, 4, 5, 6, 7], 8, 1);  // Output: 0
echo "\n";
echo maxCount([11], 7, 50);  // Output: 7
?>

Explication:

1. Convertir le tableau interdit en défini :
   
   Nous utilisons array_flip($banned) pour créer un ensemble à partir du tableau banni, ce qui permet aux recherches O(1) de vérifier si un numéro est banni.

2. Itérer de 1 à n :
   
   Nous parcourons les nombres de 1 à n. Pour chaque numéro :

   • Si le numéro ne fait pas partie de l'ensemble interdit (vérifié à l'aide d'isset($bannedSet[$i])),
   • Et si l'ajout du nombre à la somme ne dépasse pas maxSum,
   • Nous incluons ce numéro et mettons à jour la somme et le décompte.

3. Renvoyer le décompte :
   
   Après la boucle, on renvoie le nombre d'entiers sélectionnés ($count).

4. $bannedSet = array_flip($banned); : Ceci convertit la liste interdite en un ensemble (tableau associatif) pour des recherches rapides.

5. pour ($i = 1; $i  : Nous parcourons tous les entiers de 1 à n.

6. if (isset($bannedSet[$i])) { continuer ; 🎜> : Ceci vérifie si le numéro actuel fait partie de l'ensemble interdit. Si c'est le cas, nous l'ignorons.

7. if ($sum $i > $maxSum) { break; > : Si l'ajout du nombre actuel dépasse maxSum, nous arrêtons le processus.

8. $somme = $i; $count ; : Si le nombre est valide et que son ajout ne dépasse pas maxSum, nous l'incluons dans notre somme et augmentons le nombre.

Complexité temporelle :

• La création de l'ensemble interdit (array_flip) est O(b), où b est la longueur du tableau interdit.
• La boucle itère n fois (pour les nombres de 1 à n), et chaque recherche dans l'ensemble interdit prend un temps O(1). Ainsi, la complexité temporelle de la boucle est O(n).
• Ainsi, la complexité temporelle globale est O(n b), ce qui est efficace compte tenu des contraintes du problème.

Exemple de procédure pas à pas :

Pour la saisie :

• Entrée 1 : interdit = [1, 6, 5], n = 5, maxSum = 6

  • Nous créons l'ensemble interdit : {1, 5, 6}.
  • Nous parcourons les nombres 1 à 5 :
    • 1 est banni, ignorez-le.
    • 2 n'est pas interdit, ajoutez-le à la somme (somme = 2, compte = 1).
    • 3 n'est pas interdit, ajoutez-le à la somme (somme = 5, compte = 2).
    • 4 n'est pas interdit, mais l'ajouter à la somme dépasserait maxSum (5 4 = 9), alors sautez-le.
  • Le résultat est 2.

• Entrée 2 : interdit = [1, 2, 3, 4, 5, 6, 7], n = 8, maxSum = 1

  • Tous les nombres de 1 à 7 sont interdits, aucun numéro valide ne peut donc être choisi.
  • Le résultat est 0.

• Entrée 3 : interdit = [11], n = 7, maxSum = 50

  • Le seul numéro interdit est le 11, qui se situe en dehors de la plage 1 à 7.
  • Nous pouvons sélectionner tous les nombres de 1 à 7, et leur somme est 28, ce qui est inférieur à maxSum.
  • Le résultat est 7.

Cette solution gère efficacement le problème dans les limites données.

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!