Étant donné un tableau binaire, le nombre minimum d'échanges adjacents requis pour le trier

Il existe différentes méthodes qui peuvent être utilisées pour minimiser le nombre d'échanges requis entre des éléments adjacents pour obtenir un tableau trié. Le tableau de sortie donné ne contient que deux types d'éléments, à savoir 0 et 1. Nous discuterons de deux manières différentes de résoudre ce problème, où la première solution utilise un espace supplémentaire pour stocker le nombre de zéros, tandis que la seconde solution utilise uniquement un espace constant.

Énoncé du problème

On nous donne un tableau contenant seulement deux éléments, 0 et 1. Notre objectif est de trouver le nombre minimum de swaps requis pour trier un tableau binaire donné.

La traduction chinoise de

Exemple

est :

Exemple

Given Array: [1, 1, 0, 0, 0, 1, 0]
Result: 9 swaps required

La traduction chinoise de

Explication

est :

Explication

Swap 1: [0, 1, 1, 0, 0, 0, 0]
Swap 2: [0, 1, 0, 1, 0, 0, 0]
Swap 3: [0, 1, 0, 0, 1, 0, 0]
Swap 4: [0, 1, 0, 0, 0, 1, 0]
Swap 5: [0, 1, 0, 0, 0, 0, 1]
Swap 6: [0, 0, 1, 0, 0, 0, 1]
Swap 7: [0, 0, 0, 1, 0, 0, 1]
Swap 8: [0, 0, 0, 0, 1, 0, 1]
Swap 9: [0, 0, 0, 0, 0, 1, 1]

Discutons maintenant d'un moyen simple de résoudre ce problème.

Méthode 1

Dans cette méthode, nous compterons le nombre total de 0 et de 1, nous pouvons le faire en comptant le nombre de 0 qui apparaissent après chaque 1, puis en les additionnant. Comme nous le savons, tous les 1 seront à l'extrême droite du tableau et tous les 0 seront à l'extrême gauche du tableau, après tri. Cela signifie que nous devons échanger chaque 1 du tableau avec chaque 0 à sa droite. Le nombre d'échanges requis pour chaque élément du tableau sera le nombre total de 0 qui apparaissent à sa droite dans le tableau. Nous continuerons d'ajouter le nombre total de 0 qui apparaissent à gauche pour chaque 1 pour obtenir le nombre requis d'échanges.

La traduction chinoise de

Exemple

est :

Exemple

Dans l'exemple ci-dessous, nous avons créé un tableau binaire de sept nombres. Nous trouvons le nombre minimum d'échanges de voisins requis pour trier le tableau en utilisant la méthode ci-dessus.

#include <bits/stdc++.h>
using namespace std;

// this function calculates the minimum number of swaps
int minimum_number_of_swaps(int given_array[], int nums){
   int Number_of_zeroes[nums];
   memset( Number_of_zeroes, 0, sizeof(Number_of_zeroes));
   int iterator, number = 0;
   Number_of_zeroes[nums - 1] = 1 - given_array[nums - 1];
   for (iterator = nums - 2; iterator >= 0; iterator--) {
      Number_of_zeroes[iterator] = Number_of_zeroes[iterator + 1];
      if (given_array[iterator] == 0)
      Number_of_zeroes[iterator]++;
   }
   for (iterator = 0; iterator < nums; iterator++) {
      if (given_array[iterator] == 1)
      number += Number_of_zeroes[iterator];
   }
   return number;
}
// main code goes from here
int main(){
   int given_array[] = { 1, 1, 0, 0, 0, 1, 0 };
   int nums = sizeof(given_array) / sizeof(given_array[0]);
   cout  << " Minimum number of swaps required to sort the given binary array is " << minimum_number_of_swaps(given_array, nums);
   return 0;
}

Sortie

Lorsque vous exécutez le programme C++ ci-dessus, il produira le résultat suivant : 

Minimum number of swaps required to sort the given binary array is 9

Complexité temporelle de cette approche - Puisque nous itérons n fois dans une boucle, la complexité temporelle est : O(n)

Complexité spatiale - Puisque nous utilisons un tableau supplémentaire pour stocker le nombre de zéros, la complexité spatiale de cette méthode est O(n)

Examinons maintenant une solution meilleure et plus efficace pour résoudre le même problème. Notre nouvelle solution économise de la mémoire car elle ne prend pas d'espace supplémentaire.

Méthode 2

Dans cette approche, nous minimiserons l'espace auxiliaire à un espace constant. Au lieu de lire le tableau depuis le début, nous allons parcourir depuis la fin et compter le nombre de zéros que nous rencontrons. Si nous obtenons un 1, le nombre d'échanges nécessaires pour mettre ce 1 dans sa position triée est le nombre de zéros rencontrés avant lui.

La traduction chinoise de

Exemple

est :

Exemple

Ce qui suit est l'implémentation C++ de la méthode ci-dessus -

#include <iostream>
using namespace std;

// this function finds out the least number of swaps needed
int minimum_number_of_swaps(int nums[], int number){
   int c = 0;
   int zeros_unplaced = 0;
   for(int iterator=number-1;iterator>=0;iterator--){
      if(nums[iterator] == 0)
      zeros_unplaced += 1;
      if(nums[iterator] == 1)
      c += zeros_unplaced;
   }
   return c;
}
// Main code goes here
int main(){
   int nums[] = { 1, 1, 0, 0, 0, 1, 0 };
   cout<< " Minimum number of swaps required to sort the given binary array is " << minimum_number_of_swaps(nums, 7);
   return 0;
}

Sortie

Lorsque vous exécutez le programme C++ ci-dessus, il produira le résultat suivant : 

Minimum number of swaps required to sort the given binary array is 9

Complexité temporelle de cette approche - Puisque nous itérons n fois dans une boucle, la complexité temporelle est : O(n)

Complexité spatiale - Puisque nous n'utilisons aucun espace supplémentaire, la complexité spatiale est linéaire, c'est-à-dire O(1).

Dans cet article, nous avons discuté de deux méthodes de calcul du nombre minimum d'échanges requis pour trier un tableau contenant uniquement des 0 et des 1. Dans la première approche, nous avons utilisé un tableau supplémentaire pour stocker la solution à chaque étape, tandis que dans la seconde approche, nous l'avons fait dans un espace constant, ce qui a entraîné une meilleure complexité spatiale.

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!