Memandangkan tatasusunan binari, bilangan minimum swap bersebelahan yang diperlukan untuk menjadikannya diisih

Terdapat kaedah berbeza yang boleh digunakan untuk meminimumkan bilangan swap yang diperlukan antara elemen bersebelahan untuk mendapatkan tatasusunan yang diisih. Tatasusunan keluaran yang diberikan mengandungi hanya dua jenis elemen iaitu 0 dan 1. Kami akan membincangkan dua cara berbeza untuk menyelesaikan masalah ini, di mana penyelesaian pertama menggunakan ruang tambahan untuk menyimpan bilangan sifar, manakala penyelesaian kedua hanya menggunakan ruang malar.

Pernyataan Masalah

Kami diberi tatasusunan yang mengandungi hanya dua elemen, 0 dan 1. Matlamat kami adalah untuk mencari bilangan swap minimum yang diperlukan untuk mengisih tatasusunan binari yang diberikan.

Terjemahan bahasa Cina bagi

Contoh

ialah:

Contoh

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

Terjemahan bahasa Cina bagi

Penjelasan

ialah:

Penjelasan

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]

Sekarang mari kita bincangkan cara mudah untuk menyelesaikan masalah ini.

Kaedah 1

Dalam kaedah ini kita akan mengira jumlah bilangan 0s dan 1s, kita boleh melakukan ini dengan mengira bilangan 0s yang muncul selepas setiap 1 dan kemudian menambahnya. Seperti yang kita tahu, semua 1 akan berada di hujung kanan tatasusunan dan semua 0 akan berada di hujung kiri tatasusunan, selepas mengisih. Ini bermakna, kita perlu menukar setiap 1 dalam tatasusunan dengan setiap 0 di sebelah kanannya. Bilangan swap yang diperlukan untuk setiap elemen dalam tatasusunan ialah jumlah bilangan 0s yang muncul di sebelah kanannya dalam tatasusunan. Kami akan terus menambah jumlah bilangan 0 yang muncul di sebelah kiri untuk setiap 1 untuk mendapatkan bilangan swap yang diperlukan.

Terjemahan bahasa Cina bagi

Contoh

ialah:

Contoh

Dalam contoh di bawah, kami telah mencipta tatasusunan binari tujuh nombor. Kami mendapati bilangan minimum pertukaran jiran yang diperlukan untuk mengisih tatasusunan menggunakan kaedah di atas.

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

Output

Apabila anda menjalankan program C++ di atas, ia akan menghasilkan output berikut -

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

Kerumitan masa pendekatan ini - Memandangkan kita berulang n kali dalam satu gelung, kerumitan masa ialah: O(n)

Kerumitan Angkasa - Memandangkan kita menggunakan tatasusunan tambahan untuk menyimpan bilangan sifar, kerumitan ruang kaedah ini ialah O(n)

Sekarang mari kita lihat penyelesaian yang lebih baik dan lebih cekap untuk menyelesaikan masalah yang sama. Penyelesaian baharu kami menjimatkan memori kerana ia tidak mengambil sebarang ruang tambahan.

Kaedah 2

Dalam pendekatan ini, kami akan meminimumkan ruang tambahan kepada ruang malar. Daripada membaca tatasusunan dari awal, kami akan mengulangi dari akhir dan mengira bilangan semua sifar yang kami temui. Jika kita mendapat 1, bilangan swap yang diperlukan untuk meletakkan 1 itu dalam kedudukan yang disusun ialah bilangan sifar yang ditemui sebelum itu.

Terjemahan bahasa Cina bagi

Contoh

ialah:

Contoh

Berikut ialah pelaksanaan C++ bagi kaedah di atas -

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

Output

Apabila anda menjalankan program C++ di atas, ia akan menghasilkan output berikut -

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

Kerumitan masa pendekatan ini - Memandangkan kita berulang n kali dalam satu gelung, kerumitan masa ialah: O(n)

Kerumitan Angkasa - Memandangkan kami tidak menggunakan sebarang ruang tambahan, kerumitan ruang adalah linear, iaitu O(1).

Dalam artikel ini, kami membincangkan dua kaedah untuk mengira bilangan swap minimum yang diperlukan untuk mengisih tatasusunan yang mengandungi hanya 0s dan 1s. Dalam pendekatan pertama, kami menggunakan tatasusunan tambahan untuk menyimpan penyelesaian bagi setiap langkah, manakala dalam pendekatan kedua, kami melakukannya dalam ruang malar, menghasilkan kerumitan ruang yang lebih baik.

Atas ialah kandungan terperinci Memandangkan tatasusunan binari, bilangan minimum swap bersebelahan yang diperlukan untuk menjadikannya diisih. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!