Nombre maximum d'entiers à choisir dans une plage I-tutoriel php-php.cn

Nombre maximum d'entiers à choisir dans une plage I

Mary-Kate Olsen

Libérer： 2024-12-21 02:01:10

original

815 Les gens l'ont consulté

Maximum Number of Integers to Choose From a Range 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 <= banni.length <= 10⁴
1 <= interdit[i], n <= 10⁴
1 <= maxSum <= 10⁹

Indice :

Conservez les nombres interdits inférieurs à n dans un ensemble.
Faites une boucle sur les nombres de 1 à n et si le numéro n'est pas interdit, utilisez-le.
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:

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).
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.
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:

Exclure les numéros interdits : Nous garderons une trace des numéros interdits dans un ensemble (ou un tableau associatif) pour des recherches rapides.
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.
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

Explication:

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.
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.
Renvoyer le décompte :

Après la boucle, on renvoie le nombre d'entiers sélectionnés ($count).
$bannedSet = array_flip($banned); : Ceci convertit la liste interdite en un ensemble (tableau associatif) pour des recherches rapides.
pour ($i = 1; $i <= $n; $i ) : Nous parcourons tous les entiers de 1 à n.
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.
if ($sum $i > $maxSum) { break; > : Si l'ajout du nombre actuel dépasse maxSum, nous arrêtons le processus.
$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 :