Isih tatasusunan yang mengandungi unsur dua jenis

Terdapat cara yang berbeza untuk mengisih tatasusunan yang mengandungi hanya dua jenis elemen (iaitu hanya 1 dan 0). Kami akan membincangkan tiga cara berbeza untuk mencapai matlamat ini. Kaedah pertama hanya menggunakan fungsi sort() yang telah ditetapkan untuk mengisih tatasusunan yang diberikan. Kaedah kedua ialah kaedah pengiraan di mana kita akan mengira bilangan 0 dan 1 dan kemudian mengemas kini tatasusunan dengan terlebih dahulu menulis nombor 0 dan kemudian nombor 1. Dalam kaedah terakhir, kami menggunakan kaedah penunjuk berganda.

Pernyataan Masalah

Kami diberi tatasusunan yang mengandungi hanya 1s dan 0s. Tugas kita ialah menyusun semua 0s dan 1s supaya 1 berada di sebelah kanan tatasusunan dan 0 berada di sebelah kiri tatasusunan

Terjemahan bahasa Cina bagi

Contoh

ialah:

Contoh

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

Kaedah 1: Kaedah keretakan brute force.

Dalam kaedah ini, kami akan mengisih tatasusunan secara terus menggunakan fungsi sort(). Sejak 1>0, selepas mengisih, semua 1 akan disusun di sebelah kanan tatasusunan, dan semua 0 akan disusun di sebelah kiri.

Fungsi Sort(): Fungsi Sort() mengambil masa O(NlogN) dan mengembalikan tatasusunan dalam tertib menaik.

Terjemahan bahasa Cina bagi

Contoh

ialah:

Contoh

Di bawah ialah pelaksanaan C++ untuk mengisih tatasusunan yang mengandungi dua jenis elemen.

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

Output

Apabila disusun, program di atas akan menghasilkan output berikut -

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

Kaedah 2: Kaedah pengisihan mengira

Dalam kaedah ini kita hanya akan mengira nombor 0 dan 1 dalam tatasusunan dan kemudian mengemas kini tatasusunan dengan 0 pada permulaan dan 1 pada akhir.

Dengan melakukan ini, kita akan mempunyai semua 0 di bahagian paling kiri tatasusunan dan semua 1 di bahagian paling kanan tatasusunan yang secara automatik akan mewakili tatasusunan diisih yang dikehendaki.

Ini adalah kaedah yang mudah, tetapi ia memasukkan nilai baharu ke dalam tatasusunan dan bukannya menukar kedudukan mereka, jadi kaedah ini tidak cekap.

Terjemahan bahasa Cina bagi

Contoh

ialah:

Contoh

Berikut adalah pelaksanaan kaedah di atas menggunakan 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;
}

Output

Apabila disusun, ia akan menghasilkan output berikut -

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

Kerumitan Masa - Memandangkan kami hanya menggunakan satu gelung, kerumitan masa kaedah ini ialah O(N)

Kerumitan ruang - O(1). Walaupun kami menggunakan pembolehubah tambahan, kerana ia adalah linear, kerumitan ruang adalah malar.

Kaedah 3: Cara terbaik untuk menyelesaikan masalah ini

Dalam kaedah ini, kami akan menyimpan dua petunjuk, permulaan dan penamat. Kami akan melintasi secara serentak dari permulaan tatasusunan (indeks 0) menggunakan penunjuk mula dan melintasi dari hujung (indeks len-1) menggunakan penunjuk akhir.

Tugas kami adalah untuk menyusun semua 1 ke bahagian paling kanan tatasusunan, yang secara automatik akan menyusun semua 0 ke sebelah kiri tatasusunan.

Kami bermula dari indeks awal dan jika elemen yang ditemui ialah 1, kami menukarnya dengan elemen pada indeks "akhir" dan mengurangkan penunjuk akhir sebanyak 1.

Jika elemen yang ditemui ialah 0, maka tidak perlu melakukan sebarang operasi swap kerana ia sudah berada di kedudukan paling kiri, kami hanya menambah penunjuk permulaan sebanyak 1.

Terjemahan bahasa Cina bagi

Contoh

ialah:

Contoh

Berikut ialah kod untuk melaksanakan kaedah ini -

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

Output

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

Kerumitan Masa - Memandangkan kita mengulangi tatasusunan sekali sahaja, kerumitan masa pendekatan ini adalah linear, iaitu O(N)

Kerumitan Angkasa − Memandangkan kami tidak menggunakan sebarang ruang tambahan, kerumitan ruang ialah O(1).

Kesimpulan

Dalam artikel ini, kami membincangkan tiga cara berbeza untuk mengisih tatasusunan yang mengandungi hanya dua jenis elemen, iaitu hanya 1 dan 0.

Atas ialah kandungan terperinci Isih tatasusunan yang mengandungi unsur dua jenis. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!