Vérifie si le tableau donné peut former une permutation de 1 à N en divisant par deux les éléments

Notre objectif est de déterminer si l'exécution de plusieurs divisions sur chaque élément contenu dans le tableau crée une liste d'entiers de 1 à N sans aucun doublon. Le succès de cet effort signifiera que nos objectifs d’enquête auront été atteints avec succès. Essentiellement, déterminer si couper par deux tous les éléments fournis dans un tableau donné entraînerait une permutation composée entièrement de valeurs non répétitives entre 1 et N est l'objectif principal de notre travail. Une fois confirmé, l’évaluation de notre article serait la prochaine étape logique.

Grammaire

Avant d'aborder la solution proposée, il est important d'avoir une compréhension approximative de la syntaxe de la méthode que nous sommes sur le point d'implémenter.

bool canBePermutation(vector<int>& arr)
{
   // Implementation goes here
}
</int>

Algorithme

Pour résoudre ce problème, procédons étape par étape en utilisant l'algorithme décrit ci-dessous -

• Pour porter une attention particulière aux composants observés dans un tableau, commencez par démarrer une collection ou un ensemble de hachage. Ensuite, parcourez chaque élément présent dans ce tableau.

• Pour obtenir un entier compris entre 1 et N, vous devez diviser chaque élément par 2 plusieurs fois.

• Vérifiez si la valeur du résultat existe déjà dans la collection. Si c'est le cas, renvoie false car il ne peut pas y avoir de doublons dans l'arrangement.

• Pour que le tableau soit un arrangement valide, chaque élément doit remplir les conditions ci-dessus. En supposant que ce critère soit pleinement rempli, confirmer son éligibilité en fournissant une véritable valeur de retour peut être considéré comme une ligne de conduite appropriée.

Méthode

Pour résoudre efficacement ce problème. Il peut être utile d’explorer différentes stratégies. Je vais suggérer deux approches possibles -

Méthode 1 : Approche basée sur les ensembles

Créer une approche efficace nécessite l'utilisation de techniques minutieuses, comme la mise en place d'un système de suivi utilisant des collections créées pour enregistrer les composants rencontrés tout au long du processus. Cela implique d'évaluer de manière itérative chaque composant via un processus de division, en s'assurant que sa valeur résultante se situe entre 1 et N valeurs de plage, puis en vérifiant notre ensemble de traces pour validation avant d'ajouter l'élément nouvellement observé, puis en retournant s'il y a des anomalies fausses, sinon renvoie true une fois que toutes les valeurs ont réussi les contrôles d'évaluation requis par Constellation.

Exemple

#include <iostream>
#include <vector>
#include <unordered_set>

bool canBePermutation(std::vector<int>& arr) {
   std::unordered_set<int> seen;
   
   for (int num : arr) {
      while (num > 0 && num != 1) {
         if (seen.find(num) != seen.end())
            return false;
         
         seen.insert(num);
         num /= 2;
      }
      
      if (num == 0)
         return false;
   }
   
   return true;
}

int main() {
   std::vector<int> arr = {4, 2, 1, 3};
   
   if (canBePermutation(arr)) {
      std::cout << "The given array can be transformed into a permutation.";
   } else {
      std::cout << "The given array cannot be transformed into a permutation.";
   }
   
   return 0;
}

Sortie

The given array cannot be transformed into a permutation.

Instructions

Les premières étapes de la méthode 1 consistent à configurer un ensemble non ordonné pour garder une trace des éléments présents dans le tableau. Cette méthode de codage continue ensuite à parcourir chaque élément du même tableau, en les divisant par 2 à chaque fois, en les réduisant de manière répétée à un nombre entier compris entre 1 et N. Au cours de ces itérations, une vérification est effectuée pour voir si un élément qui semble avoir été créé a déjà été créé dans la même collection, essayant ainsi d'éviter les permutations en double simplement dues à la duplication. Lorsqu'un doublon résultant de ces permutations répétitives est détecté, false est renvoyé, comme lorsque tout est vérifié sans qu'un doublon soit complété - passé comme vrai - indiquant effectivement si l'ensemble donné peut être déplacé dans sa permutation respective, tout en minimisant ses composants en les divisant par deux. eux.

Méthode 2 : Méthode de tri

Le tri croissant permet de détecter si chaque élément du tableau peut s'afficher comme une valeur correspondante dans la liste triée. Si aucun des éléments ne répond à ce critère, notre sortie produira faux ; cependant, si tous les éléments réussissent ce test, elle renverra vrai.

Exemple

#include <iostream>
#include <vector>
#include <algorithm>

bool canBePermutation(std::vector<int>& arr) {
   std::sort(arr.begin(), arr.end());

   for (int i = 0; i < arr.size(); i++) {
      int expected = i + 1;
      while (arr[i] > 0 && arr[i] != expected)
         arr[i] /= 2;

      if (arr[i] != expected)
         return false;
   }
   
   return true;
}

int main() {
   std::vector<int> arr = {4, 2, 1, 3};
   
   if (canBePermutation(arr)) {
      std::cout << "The given array can be transformed into a permutation.";
   } else {
      std::cout << "The given array cannot be transformed into a permutation.";
   }
   
   return 0;
}

Sortie

The given array can be transformed into a permutation.

Instructions

Selon la méthode 2 (méthode de tri), nous trions d'abord le tableau d'entrée d'origine par ordre croissant avant de vérifier davantage la routine de code. Le code exécute ensuite diverses itérations sur chaque élément individuel du tableau ci-dessus tout en vérifiant s'ils sont divisibles par deux jusqu'à ce qu'ils atteignent une valeur spécifiée et supposée établie en fonction de leur position dans la plage de valeurs d'index nouvellement triée. S'il y a des cas dans une telle itération qui ne remplissent pas ces conditions clés prédéfinies, alors notre code décrit le résultat comme « Faux », ce qui signifie qu'il n'est pas possible de convertir ce tableau dans l'arrangement séquentiel correspondant. Dans le même temps, à l’inverse, chaque élément conforme produit un « vrai » résultat, fournissant une direction positive réalisable pour nos objectifs de réorganisation du réseau.

Conclusion

Dans cet article, nous abordons le défi consistant à vérifier si un tableau donné peut être transformé en une permutation contenant des nombres compris entre 1 et N en divisant par deux ses éléments. Nous fournissons au lecteur les grandes lignes, la syntaxe et les procédures algorithmiques permettant de résoudre efficacement ce problème. De plus, nous proposons deux approches possibles ainsi que des exemples complets de code exécutable C++. En appliquant les techniques basées sur les ensembles ou les stratégies de tri mises en évidence dans cet article, le lecteur peut déterminer à sa satisfaction si un tableau donné remplit toutes les conditions nécessaires pour un arrangement juridique.

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!