Bei einem gegebenen binären Array ist dies die Mindestanzahl benachbarter Swaps, die erforderlich sind, um es zu sortieren

Es gibt verschiedene Methoden, mit denen die Anzahl der erforderlichen Austauschvorgänge zwischen benachbarten Elementen minimiert werden kann, um ein sortiertes Array zu erhalten. Das angegebene Ausgabearray enthält nur zwei Arten von Elementen, nämlich 0 und 1. Wir werden zwei verschiedene Möglichkeiten zur Lösung dieses Problems diskutieren, wobei die erste Lösung zusätzlichen Speicherplatz zum Speichern der Anzahl der Nullen verwendet, während die zweite Lösung nur konstanten Speicherplatz verwendet.

Problemstellung

Wir erhalten ein Array, das nur zwei Elemente enthält, 0 und 1. Unser Ziel ist es, die Mindestanzahl an Swaps zu finden, die zum Sortieren eines bestimmten Binärarrays erforderlich sind.

Die chinesische Übersetzung von

Beispiel

lautet:

Beispiel

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

Die chinesische Übersetzung von

Erklärung

lautet:

Erklärung

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]

Lassen Sie uns nun einen einfachen Weg zur Lösung dieses Problems besprechen.

Methode 1

Bei dieser Methode zählen wir die Gesamtzahl der Nullen und Einsen. Dies können wir tun, indem wir die Anzahl der Nullen zählen, die nach jeder Eins erscheinen, und diese dann addieren. Wie wir wissen, befinden sich nach der Sortierung alle Einsen ganz rechts im Array und alle Nullen ganz links im Array. Das bedeutet, dass wir jede 1 im Array mit jeder 0 rechts davon vertauschen müssen. Die Anzahl der für jedes Element im Array erforderlichen Swaps entspricht der Gesamtzahl der Nullen, die rechts davon im Array erscheinen. Wir addieren weiterhin die Gesamtzahl der Nullen, die links für jede Eins angezeigt werden, um die erforderliche Anzahl an Swaps zu erhalten.

Die chinesische Übersetzung von

Beispiel

lautet:

Beispiel

Im folgenden Beispiel haben wir ein binäres Array mit sieben Zahlen erstellt. Mit der oben genannten Methode ermitteln wir die Mindestanzahl an Nachbaraustauschvorgängen, die zum Sortieren des Arrays erforderlich sind.

#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;
}

Ausgabe

Wenn Sie das obige C++-Programm ausführen, wird die folgende Ausgabe erzeugt:

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

Zeitliche Komplexität dieses Ansatzes – Da wir n-mal in einer Schleife iterieren, beträgt die zeitliche Komplexität: O(n)

Raumkomplexität – Da wir ein zusätzliches Array verwenden, um die Anzahl der Nullen zu speichern, beträgt die Raumkomplexität dieser Methode O(n)

Jetzt schauen wir uns eine bessere und effizientere Lösung zur Lösung desselben Problems an. Unsere neue Lösung spart Speicher, da sie keinen zusätzlichen Platz beansprucht.

Methode 2

Bei diesem Ansatz minimieren wir den Hilfsraum auf einen konstanten Raum. Anstatt das Array von Anfang an zu lesen, iterieren wir vom Ende und zählen die Anzahl aller Nullen, auf die wir stoßen. Wenn wir eine 1 erhalten, entspricht die Anzahl der Vertauschungen, die erforderlich sind, um diese 1 an ihre sortierte Position zu bringen, der Anzahl der davor angetroffenen Nullen.

Die chinesische Übersetzung von

Beispiel

lautet:

Beispiel

Das Folgende ist die C++-Implementierung der oben genannten Methode -

#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;
}

Ausgabe

Wenn Sie das obige C++-Programm ausführen, wird die folgende Ausgabe erzeugt:

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

Zeitliche Komplexität dieses Ansatzes – Da wir n-mal in einer Schleife iterieren, beträgt die zeitliche Komplexität: O(n)

Raumkomplexität – Da wir keinen zusätzlichen Raum verwenden, ist die Raumkomplexität linear, d. h. O(1).

In diesem Artikel haben wir zwei Methoden zur Berechnung der Mindestanzahl an Swaps besprochen, die zum Sortieren eines Arrays erforderlich sind, das nur Nullen und Einsen enthält. Beim ersten Ansatz haben wir ein zusätzliches Array verwendet, um die Lösung für jeden Schritt zu speichern, während wir beim zweiten Ansatz dies in einem konstanten Raum getan haben, was zu einer besseren Raumkomplexität führte.

Das obige ist der detaillierte Inhalt vonBei einem gegebenen binären Array ist dies die Mindestanzahl benachbarter Swaps, die erforderlich sind, um es zu sortieren. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!