Rechercher si le tableau peut être trié

3011. Rechercher si le tableau peut être trié

Difficulté :Moyen

Sujets : Tableau, manipulation de bits, tri

Vous recevez un tableau indexé à 0 de nombres entiers positifs.

En une seule opération, vous pouvez échanger deux éléments adjacents s'ils ont le même nombre de bits définis¹. Vous êtes autorisé à effectuer cette opération n'importe quel nombre de fois (y compris zéro).

Renvoyer true si vous pouvez trier le tableau, sinon renvoyer false.

Exemple 1 :

• Entrée : nums = [8,4,2,30,15]
• Sortie : vrai
• Explication : Regardons la représentation binaire de chaque élément. Les nombres 2, 4 et 8 ont chacun un bit défini avec une représentation binaire « 10 », « 100 » et « 1000 » respectivement. Les nombres 15 et 30 ont quatre bits définis chacun avec une représentation binaire « 1111 » et « 11110 ». Nous pouvons trier le tableau en utilisant 4 opérations :
  • Échangez les numéros[0] avec les numéros[1]. Cette opération est valide car 8 et 4 ont chacun un bit défini. Le tableau devient [4,8,2,30,15].
  • Échangez les numéros[1] avec les numéros[2]. Cette opération est valide car 8 et 2 ont chacun un bit défini. Le tableau devient [4,2,8,30,15].
  • Échangez les numéros[0] avec les numéros[1]. Cette opération est valide car 4 et 2 ont chacun un bit défini. Le tableau devient [2,4,8,30,15].
  • Échangez les numéros[3] avec les numéros[4]. Cette opération est valide car 30 et 15 ont chacun quatre bits définis. Le tableau devient [2,4,8,15,30].
  • Le tableau est devenu trié, nous retournons donc vrai.
  • Notez qu'il peut y avoir d'autres séquences d'opérations qui trient également le tableau.

Exemple 2 :

• Entrée : nums = [1,2,3,4,5]
• Sortie : vrai
• Explication : Le tableau est déjà trié, nous renvoyons donc vrai.

Exemple 3 :

• Entrée : nums = [3,16,8,4,2]
• Sortie : faux
• Explication : On peut montrer qu'il n'est pas possible de trier le tableau d'entrée en utilisant un certain nombre d'opérations.

Exemple 4 :

• Entrée : nums = [75,34,30]
• Sortie : faux
• Explication : On peut montrer qu'il n'est pas possible de trier le tableau d'entrée en utilisant un certain nombre d'opérations.

Contraintes :

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 2⁸

Indice :

1. Divisez le tableau en segments. Chaque segment contient des éléments consécutifs avec le même nombre de bits définis.
2. De gauche à droite, le plus grand élément du segment précédent doit être plus petit que le plus petit élément du segment actuel.

Solution :

Nous devons déterminer si le tableau peut être trié en échangeant uniquement les éléments adjacents qui ont le même nombre de bits définis dans leur représentation binaire. Voici le plan :

Étapes de la solution :

1. Observation clé : L'opération nous permet d'échanger des éléments adjacents uniquement s'ils ont le même nombre de bits définis. Cela restreint l'échange entre des éléments avec un nombre différent de bits définis.

2. Plan :

   • Regroupez les éléments par le nombre de bits définis dans leur représentation binaire.
   • Triez chaque groupe individuellement, car au sein d'un groupe, les éléments peuvent être réorganisés par échanges.
   • Après avoir trié chaque groupe, fusionnez les groupes triés ensemble.
   • Vérifiez si ce tableau fusionné est trié. Si tel est le cas, il est possible de trier le tableau à l'aide des opérations autorisées.

3. Étapes :

   • Comptez les bits définis dans chaque numéro et regroupez les numéros avec le même nombre de bits définis.
   • Triez chaque groupe individuellement.
   • Reconstruisez le tableau à partir de ces groupes triés et vérifiez si le résultat est trié.

Implémentons cette solution en PHP : 3011. Rechercher si le tableau peut être trié

<?php
/**
 * Helper function to count set bits in a number
 *
 * @param $n
 * @return int
 */
function countSetBits($n) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * @param Integer[] $nums
 * @return Boolean
 */
function canSortArray($nums) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
$nums1 = [8, 4, 2, 30, 15];
$nums2 = [1, 2, 3, 4, 5];
$nums3 = [3, 16, 8, 4, 2];
$nums4 = [75, 34, 30];

echo canBeSorted($nums1) ? 'true' : 'false'; // Expected output: true
echo "\n";
echo canBeSorted($nums2) ? 'true' : 'false'; // Expected output: true
echo "\n";
echo canBeSorted($nums3) ? 'true' : 'false'; // Expected output: false
echo "\n";
echo canBeSorted($nums4) ? 'true' : 'false'; // Expected output: false
?>





  
  
  Explication:




Fonction countSetBits : compte le nombre de bits définis dans un nombre à l'aide d'opérations au niveau du bit.

Regroupement d'éléments : bitGroups est un tableau associatif où chaque clé représente le nombre de bits défini et chaque valeur est un tableau de nombres avec autant de bits définis.

Tri et Reconstruction :


Nous parcourons les nombres pour regrouper les éléments en fonction de leur nombre de bits défini.
Nous trions chaque groupe indépendamment.
Nous reconstruisons ensuite le tableau en insérant chaque élément du groupe trié dans son ordre d'origine.
Enfin, on vérifie si le tableau reconstruit est trié dans un ordre non décroissant. Si c'est le cas, retournez true ; sinon, retournez false.


Comparaison finale : Comparez le tableau reconstruit avec une version entièrement triée de nums. S'ils correspondent, retournez true ; sinon, renvoie false.



  
  
  Analyse de complexité




Complexité temporelle : O(n log n) en raison du tri au sein de chaque groupe et de la comparaison finale.

Complexité spatiale : O(n) pour stocker les groupes de bits.


Cette solution garantit que nous échangeons uniquement les éléments adjacents avec le même nombre de bits défini, obtenant un ordre trié si possible.

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








Set Bit Un bit défini fait référence à un bit dans la représentation binaire d'un nombre qui a une valeur de 1. ↩





          

            
  

            
        
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!