La plus grande combinaison avec Bitwise ET supérieur à zéro

2275. La plus grande combinaison avec Bitwise ET supérieur à zéro

Difficulté :Moyen

Sujets : Tableau, table de hachage, manipulation de bits, comptage

Le ET au niveau du bit d'un tableau nums est le ET au niveau du bit de tous les entiers en nombres.

• Par exemple, pour nums = [1, 5, 3], le ET au niveau du bit est égal à 1 & 5 & 3 = 1.
• De plus, pour nums = [7], le ET au niveau du bit est 7.

Vous recevez un tableau de candidats entiers positifs. Évaluez le ET au niveau du bit de chaque combinaison de nombres de candidats. Chaque numéro des candidats ne peut être utilisé que une seule fois dans chaque combinaison.

Renvoyer la taille de la plus grande combinaison de candidats avec un ET au niveau du bit supérieur à 0.

Exemple 1 :

• Entrée : candidats = [16,17,71,62,12,24,14]
• Sortie : 4
• Explication : La combinaison [16,17,62,24] a un ET au niveau du bit de 16 & 17 & 62 & 24 = 16 > 0.
  • La taille de la combinaison est 4.
  • On peut montrer qu'aucune combinaison avec une taille supérieure à 4 n'a un ET au niveau du bit supérieur à 0.
  • Notez que plusieurs combinaisons peuvent avoir la plus grande taille.
  • Par exemple, la combinaison [62,12,24,14] a un ET au niveau du bit de 62 & 12 & 24 & 14 = 8 > 0.

Exemple 2 :

• Entrée : candidats = [8,8]
• Sortie : 2
• Explication : La plus grande combinaison [8,8] a un ET au niveau du bit de 8 & 8 = 8 > 0.
  • La taille de la combinaison est 2, donc on renvoie 2.

Contraintes :

• 1 <= candidats.length <= 10⁵
• 1 <= candidats[i] <= 10⁷

Indice :

1. Pour que le ET au niveau du bit soit supérieur à zéro, au moins un bit doit être 1 pour chaque nombre de la combinaison.
2. Les candidats ont une longueur de 24 bits, donc pour chaque position de bit, nous pouvons calculer la taille de la plus grande combinaison de telle sorte que le ET au niveau du bit aura un 1 à cette position de bit.

Solution :

Nous devons nous concentrer sur l'identification des groupes de nombres où au moins une position de bit dans leur représentation binaire reste définie (1) sur tous les nombres de la combinaison.

Aperçu de la solution

1. Analyse des bits : Puisque chaque nombre dans les candidats peut être représenté par un nombre binaire avec jusqu'à 24 bits (comme 1 <= candidats[i] <= 10^7), il suffit d'examiner chaque position de bit de 0 à 23.

2. Compter les bits définis à chaque position : Pour chaque position de bit, comptez combien de nombres chez les candidats ont ce bit défini sur 1. Si plusieurs nombres partagent un bit dans la même position, ils pourraient former potentiellement une combinaison avec un ET au niveau du bit supérieur à zéro à cette position de bit.

3. Trouver le plus grand nombre : Le plus grand nombre de nombres avec un bit défini à une position donnée sera la réponse, car il représente la plus grande combinaison possible où le résultat ET au niveau du bit est supérieur à zéro.

Exemple

Considérez les candidats = [16, 17, 71, 62, 12, 24, 14] :

• Convertissez chaque nombre en binaire et analysez les positions des bits.
• Comptez combien de fois chaque bit est défini sur tous les nombres.
• Trouvez le nombre maximum sur toutes les positions de bits.

Implémentons cette solution en PHP : 2275. La plus grande combinaison avec Bitwise ET supérieur à zéro

  
  
  Explication:




Boucle sur chaque position de bit : Nous parcourons chaque position de bit de 0 à 23.

Compter les nombres avec jeu de bits : pour chaque position, comptez combien de nombres chez les candidats ont ce jeu de bits spécifique.

Mettre à jour la taille maximale de la combinaison : suivez le nombre le plus élevé sur toutes les positions de bits.

Renvoyer le résultat : Le résultat est la plus grande taille de combinaison avec un ET au niveau du bit supérieur à zéro, si nécessaire.



  
  
  Analyse de complexité




Complexité temporelle : O(n x 24) = O(n), où n est le nombre de éléments dans les candidats, car nous effectuons 24 opérations (une pour chaque position de bit) pour chaque nombre.

Complexité spatiale : O(1), puisque nous n'utilisons qu'une quantité fixe d'espace supplémentaire.


Cette approche est suffisamment efficace pour gérer la limite de taille d'entrée (candidates.length <= 105).

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!