2275. La plus grande combinaison avec le bit et supérieur à zéro

difficulté: medium

sujets: array, table de hachage, manipulation de bits, compter

Le bitwise et d'un tableau nums est le bitwise et de tous les entiers en nums.

• Par exemple, pour nums = [1, 5, 3], le bitwise et est égal à 1 & 5 & 3 = 1.
• Aussi, pour nums = [7], le bitwise et est 7.

Vous avez un tableau de candidats entiers positifs. Évaluez le bitwise et de chaque combinaison de nombres de candidats. Chaque nombre dans les candidats ne peut être utilisé une fois dans chaque combinaison.

return la taille de la combinaison la plus grande de candidats avec un bitwise et grand que 0 .

Exemple 1:

• entrée: candidats = [16,17,71,62,12,24,14]
• output: 4
• Explication: La combinaison [16,17,62,24] a un bit et 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 bit et supérieur à 0.
  • Notez que plus d'une combinaison peut avoir la plus grande taille.
  • Par exemple, la combinaison [62,12,24,14] a un bit et de 62 & 12 & 24 & 14 = 8> 0.

Exemple 2:

• entrée: candidats = [8,8]
• output: 2
• Explication: La plus grande combinaison [8,8] a un bit et 8 & 8 = 8> 0.
  • La taille de la combinaison est 2, donc nous retournons 2.

contraintes:

• 1 5
• 1 7

Indice:

1. pour le bitwise et pour être supérieur à zéro, au moins un bit devrait être 1 pour chaque numéro de la combinaison.
2. Les candidats mesurent 24 bits de long, donc pour chaque position de bit, nous pouvons calculer la taille de la plus grande combinaison de telle sorte que le bit et aura un 1 à cette position de bits.

Solution:

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

Aperçu de la solution

1. Analyse de bits : Étant donné que chaque numéro dans les candidats peut être représenté par un numéro binaire avec jusqu'à 24 bits (comme 1

2. compter les bits de définition à chaque position : pour chaque position de bits, comptez combien de nombres dans les candidats ont ce bit réglé sur 1. Si plusieurs nombres partagent un peu dans la même position.

3. Trouvez 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 combinaison la plus importante possible où le bit et le résultat est supérieur à zéro.

Exemple

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

• Comptez combien de fois chaque bit est défini sur tous les nombres.
• Trouvez le nombre maximum sur toutes les positions de bit.
implémentons cette solution dans php:

php / ** * @param entier [] $ candidats * @return entier * / Fonction GregestCombination ($ candidats) { ... ... ... / ** * Allez sur ./solution.php * / } // Exemple d'utilisation $ candidats = [16, 17, 71, 62, 12, 24, 14]; Echo GregestCombination ($ candidats); // Sortie: 4 ?>

Loop via chaque position de bit
1. : nous itré sur chaque position de bit de 0 à 23.
Compter les nombres avec les bits set
2. : Pour chaque position, comptez combien de nombres dans les candidats ont ce bit spécifique.
Mettre à jour la taille maximale de la combinaison
3. : suivez le nombre le plus élevé dans toutes les positions de bits.
Renvoie le résultat
4. : le résultat est la plus grande taille combinée avec un bit et supérieur à zéro, comme requis.
Analyse de complexité

complexité temporelle
• : o (n x 24) = o (n) , où n est le nombre d'éléments dans les candidats, car nous effectuons 24 opérations (une pour chaque position de bit) pour chaque nombre.
Complexité de l'espace
• : 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 (candidats.length 5

).

liens de contact

Si vous avez trouvé cette série utile, veuillez envisager de donner le référentiel

une étoile sur GitHub ou de partager le message sur vos réseaux sociaux préférés ?. Votre soutien signifierait beaucoup pour moi! Si vous voulez un contenu plus utile comme celui-ci, n'hésitez pas à me suivre:

linkedIn
github