Réorganisez un tableau pour que arr devienne arr] et n'utilisez que l'espace supplémentaire O(1), implémenté en C++

Nous obtenons un tableau de type entier positif, disons, arr[] d'une taille donnée, de telle sorte que la valeur de l'élément dans le tableau doit être supérieure à 0 mais inférieure à la taille du tableau. La tâche est de réorganiser Un tableau qui transforme uniquement arr[i] en arr[arr[i]] dans l'espace O(1) donné et imprime le résultat final.

Examinons différents scénarios d'entrée et de sortie pour cette situation −

input− int arr[] = {0 3 2 1 5 4 }

output− Tableau avant tri : 0 3 2 1 5 4 Réorganisez le tableau pour que arr[i] devienne arr[arr[i]], avec O(1) espace supplémentaire : 0 1 2 3 4 5

Explication− On nous donne un tableau entier de taille 6, et tout les éléments du tableau ont des valeurs inférieures à 6. Maintenant, nous allons réorganiser le tableau de sorte que arr[arr[0] vaut 0, arr[arr[1]] vaut 1, arr[arr [2]] vaut 2, arr[arr[3]] vaut 3, arr[ arr[4]] vaut 4, arr[arr[5]] vaut 5. Par conséquent, le tableau final après réarrangement est 0 1 2 3 4 5.

input− int arr[] = {1, 0}

output− Tableau avant permutation : 1 0 Réorganisez le tableau de sorte que arr[i] devienne arr[arr[i]], où O(1) l'espace supplémentaire est : 0 1

Explication - Nous obtenons un entier de taille 2 et tous les éléments du tableau ont des valeurs ​​inférieur à un tableau de 2. Maintenant, nous allons réorganiser le tableau pour que arr[arr[0] soit 1 et arr[arr[1]] soit 0. Par conséquent, le tableau final après réarrangement est 0 1.

Input− int arr[] = {1, 0, 2, 3}

Output−Tableau avant tri : 1 0 2 3 Réorganisez le tableau pour que arr[i] devienne arr[arr[i]] avec O(1) espace supplémentaire : 0 1 2 3

Explication - On nous donne un tableau d'entiers de taille 4 et le tableau Tous les éléments in ont une valeur inférieure à 4. Maintenant, nous allons réorganiser le tableau de sorte que arr[arr[0] vaut 0, arr[arr[1]] vaut 1, arr[arr[2] ]] vaut 2 et arr[arr[3]] vaut 3. Par conséquent, le tableau final après réarrangement est 0 1 2 3.

La méthode utilisée dans le programme suivant est la suivante

• Saisissez un tableau d'éléments entiers, calculez la taille du tableau

• Imprimez le tableau avant l'arrangement et appelez la fonction Réarrangement (arr, taille)

• Réarrangement interne de la fonction (arr, taille)

  • Démarrez la boucle FOR de i à 0 jusqu'à ce que i soit inférieur à la taille. À l'intérieur de la boucle, définissez temp sur arr[arr[i]] % size et arr[i] += temp * size.

  • Commencez à boucler FOR de i à 0 jusqu'à ce que i soit inférieur à la taille. Dans la boucle, définissez arr[i] = arr[i] / size

• pour imprimer le résultat.

Exemple

#include <bits/stdc++.h>
using namespace std;
void Rearrangement(int arr[], int size){
   for(int i=0; i < size; i++){
      int temp = arr[arr[i]] % size;
      arr[i] += temp * size;
   }
   for(int i = 0; i < size; i++){
      arr[i] = arr[i] / size;
   }
}
int main(){
   //input an array
   int arr[] = {0, 3, 2, 1, 5, 4};
   int size = sizeof(arr) / sizeof(arr[0]);
   //print the original Array
   cout<<"Array before Arrangement: ";
   for (int i = 0; i < size; i++){
      cout << arr[i] << " ";
   }
   //calling the function to rearrange the array
   Rearrangement(arr, size);
   //print the array after rearranging the values
   cout<<"\nRearrangement of an array so that arr[i] becomes arr[arr[i]] with O(1) extra space is: ";
   for(int i = 0; i < size; i++){
      cout<< arr[i] << " ";
   }
   return 0;
}

Output

Si nous exécutons le code ci-dessus, il générera la sortie suivante

Array before Arrangement: 0 3 2 1 5 4
Rearrangement of an array so that arr[i] becomes arr[arr[i]] with O(1) extra space is: 0 1 2 3 4 5

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!