Retourner les colonnes pour un nombre maximum de lignes égales

1072. Retournez les colonnes pour un nombre maximum de lignes égales

Difficulté :Moyen

Sujets : Tableau, table de hachage, matrice

Vous recevez une matrice matricielle binaire m x n.

Vous pouvez choisir n'importe quel nombre de colonnes dans la matrice et retourner chaque cellule de cette colonne (c'est-à-dire changer la valeur de la cellule de 0 à 1 ou vice versa).

Renvoyer le nombre maximum de lignes dont toutes les valeurs sont égales après un certain nombre de retournements.

Exemple 1 :

• Entrée : matrice = [[0,1],[1,1]]
• Sortie : 1
• Explication : Après avoir retourné aucune valeur, 1 ligne a toutes les valeurs égales.

Exemple 2 :

• Entrée : matrice = [[0,1],[1,0]]
• Sortie : 2
• Explication : Après avoir inversé les valeurs dans la première colonne, les deux lignes ont des valeurs égales.

Exemple 3 :

• Entrée : matrice = [[0,0,0],[0,0,1],[1,1,0]]
• Sortie : 2
• Explication : Après avoir inversé les valeurs dans les deux premières colonnes, les deux dernières lignes ont des valeurs égales.

Contraintes :

• m == matrice.longueur
• n == matrice[i].longueur
• 1 <= m, n <= 300
• matrice[i][j] vaut 0 ou 1.

Indice :

1. Inverser un sous-ensemble de colonnes revient à effectuer un XOR au niveau du bit d'un certain nombre K sur chaque ligne. Nous voulons des lignes X avec X ^ K = tous les 0 ou tous les 1. C'est la même chose que X = X^K ^K = (tous les 0 ou tous les 1) ^ K, nous voulons donc compter les lignes qui ont des bits opposés définis. Par exemple, si K = 1, alors on compte les lignes X = (00000...001, ou 1111....110).

Solution :

Nous pouvons utiliser une carte de hachage pour regrouper des lignes qui peuvent être rendues identiques en retournant certaines colonnes. Les lignes qui peuvent être rendues identiques ont soit le même motif, soit un motif complémentaire (négation au niveau du bit).

Voici la solution étape par étape :

Algorithme:

1. Pour chaque rang, calculez son motif et son motif complémentaire :
   • Le motif est la rangée telle quelle.
   • Le motif complémentaire est le résultat de l'inversion de tous les bits de la rangée.
2. Utilisez une carte de hachage pour compter les occurrences de modèles et leurs compléments.
3. Le nombre maximum pour un motif unique ou son complément donne le résultat.

Implémentons cette solution en PHP : 1072. Retournez les colonnes pour un nombre maximum de lignes égales

  
  
  Explication:




Motif et complément :


Pour chaque ligne, le motif est la ligne concaténée (par exemple, 010).
Le complément retourne tous les bits de la ligne (par exemple, 101).



Hash Map : Comptez les occurrences de chaque motif et son complément. Cela permet de regrouper les lignes qui peuvent être rendues identiques.

Nombre maximum : Recherchez le nombre maximum d'un seul motif ou de son complément pour déterminer combien de lignes peuvent être rendues identiques.



  
  
  Complexité:




Complexité temporelle : O(m x n), où m est le nombre de lignes et n est le nombre de colonnes.

Complexité spatiale : O(m x n), pour stocker des modèles dans la carte de hachage.


Cette solution respecte les contraintes et est efficace pour la taille du problème.

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!