Sortieren Sie ein Array, das Elemente zweier Typen enthält

Es gibt verschiedene Möglichkeiten, ein Array zu sortieren, das nur zwei Arten von Elementen enthält (d. h. nur 1 und 0). Wir werden drei verschiedene Wege besprechen, um dieses Ziel zu erreichen. Die erste Methode verwendet einfach die vordefinierte Funktion sort(), um das angegebene Array zu sortieren. Die zweite Methode ist die zählende Sortiermethode, bei der wir die Anzahl der Nullen und Einsen zählen und dann das Array aktualisieren, indem wir zuerst die Anzahl der Nullen und dann die Anzahl der Einsen schreiben. Bei der letzten Methode haben wir die Doppelzeigermethode verwendet.

Problemstellung

Wir erhalten ein Array, das nur Einsen und Nullen enthält. Unsere Aufgabe besteht darin, alle Nullen und Einsen so anzuordnen, dass sich 1 ganz rechts im Array und 0 ganz links im Array befindet

Die chinesische Übersetzung von

Beispiel

lautet:

Beispiel

Given array: a[] = [ 1, 1, 0, 1, 0, 1, 0, 1 ]
Resultant array: a[] = [ 0, 0, 0, 1, 1, 1, 1, 1 ]

Methode 1: Brute-Force-Cracking-Methode.

Bei dieser Methode sortieren wir das Array direkt mit der Funktion sort(). Da 1>0 ist, werden nach der Sortierung alle Einsen auf der rechten Seite des Arrays und alle Nullen auf der linken Seite angeordnet.

Sort()-Funktion: Die Sort()-Funktion benötigt O(NlogN) Zeit und gibt das Array in aufsteigender Reihenfolge zurück.

Die chinesische Übersetzung von

Beispiel

lautet:

Beispiel

Nachfolgend finden Sie eine C++-Implementierung zum Sortieren eines Arrays, das zwei Arten von Elementen enthält.

#include <bits/stdc++.h>
using namespace std;
int main(){
   int a[] = { 1, 1, 0, 1, 0, 1, 0, 1 };
   int len = sizeof(a) / sizeof( a[0] );
   
   // sort function to
   // sort the array
   sort( a, a + len);
   cout<< " After sorting the array, the array obtained is ";
   for(int iterator =0; iterator<len; iterator++){
      cout << a[iterator] <<" ";
   }
   return 0;
}

Ausgabe

Beim Kompilieren erzeugt das obige Programm die folgende Ausgabe:

After sorting the array, the array obtained is 0 0 0 1 1 1 1 1

Methode 2: Sortiermethode zählen

Bei dieser Methode zählen wir einfach die Anzahl von 0 und 1 im Array und aktualisieren dann das Array mit 0 am Anfang und 1 am Ende.

Auf diese Weise haben wir alle Nullen im äußersten linken Teil des Arrays und alle Einsen im äußersten rechten Teil des Arrays, was automatisch das gewünschte sortierte Array darstellt.

Dies ist eine einfache Methode, aber sie fügt neue Werte in das Array ein, anstatt nur ihre Positionen zu vertauschen, sodass diese Methode nicht effizient ist.

Die chinesische Übersetzung von

Beispiel

lautet:

Beispiel

Das Folgende ist die Implementierung der obigen Methode mit C++.

#include <iostream>
using namespace std;
int main() {
   int count = 0 ;
   int a[] = { 1, 1, 0, 1, 0, 1, 0, 1 };
   int len = sizeof(a) / sizeof(a[0]);
   for(int iterator=0; iterator<len; iterator++){
      if( a[iterator] == 0 )
      count++;
   }
   for(int iterator=0 ; iterator<len ; iterator++){
      if(count){
         a[iterator] = 0 ;
         count-- ;
      }
      else a[iterator] = 1;
   }
   cout<< " After sorting the array, the array obtained is ";
   for(int iterator =0 ; iterator<len ; iterator++){
      cout<< a[iterator] << " ";
   }
   return 0;
}

Ausgabe

Beim Kompilieren wird die folgende Ausgabe erzeugt:

After sorting the array, the array obtained is 0 0 0 1 1 1 1 1

Zeitkomplexität – Da wir nur eine Schleife verwendet haben, beträgt die Zeitkomplexität dieser Methode O(N)

Raumkomplexität - O(1). Obwohl wir zusätzliche Variablen verwenden, ist die Raumkomplexität konstant, da diese linear sind.

Methode 3: Der beste Weg, dieses Problem zu lösen

Bei dieser Methode behalten wir zwei Zeiger bei, Anfang und Ende. Wir werden gleichzeitig vom Anfang des Arrays (Index 0) mit dem Startzeiger und vom Ende (Index len-1) mit dem Endzeiger traversieren.

Unsere Aufgabe besteht darin, alle Einsen auf der äußersten rechten Seite des Arrays anzuordnen, wodurch automatisch alle Nullen auf der linken Seite des Arrays angeordnet werden.

Wir beginnen mit dem Anfangsindex und wenn das gefundene Element 1 ist, tauschen wir es mit dem Element am Index „Ende“ aus und dekrementieren den Endzeiger um 1.

Wenn das gefundene Element 0 ist, besteht keine Notwendigkeit, einen Austauschvorgang durchzuführen, da es sich bereits an der Position ganz links befindet. Wir erhöhen lediglich den Startzeiger um 1.

Die chinesische Übersetzung von

Beispiel

lautet:

Beispiel

Hier ist der Code zur Implementierung dieser Methode -

#include <bits/stdc++.h>
using namespace std;
int main(){
   int start =0 ;
   int a[] = { 1, 1, 0, 1, 0, 1, 0, 1 } ;
   int len = sizeof(a) / sizeof( a[0] ) ;
   int end = len-1;
   while(start < end){
      if( a[start] ==1){
         swap(a[start], a[end]);
         end--;
      }
      else
         start++;
   }
   cout<< " After sorting the array, the array obtained is ";
   for(int iterator =0 ; iterator<len ; iterator++){
      cout<< a[iterator] << " ";
   }
   return 0;
}

Ausgabe

After sorting the array, the array obtained is 0 0 0 1 1 1 1 1

Zeitkomplexität – Da wir das Array nur einmal durchlaufen, ist die Zeitkomplexität dieses Ansatzes linear, d. h. O(N)

Raumkomplexität − Da wir keinen zusätzlichen Raum verwenden, ist die Raumkomplexität O(1).

Fazit

In diesem Artikel haben wir drei verschiedene Möglichkeiten besprochen, ein Array zu sortieren, das nur zwei Arten von Elementen enthält, d. h. nur 1 und 0.

Das obige ist der detaillierte Inhalt vonSortieren Sie ein Array, das Elemente zweier Typen enthält. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!