Dalam C++, gunakan ruang tambahan O(1) untuk menyusun semula tatasusunan supaya item positif dan negatif silih berganti

Kami mendapat tatasusunan jenis integer yang mengandungi nombor positif dan negatif, katakan, arr[] sebarang saiz tertentu. Tugasnya adalah untuk menyusun semula tatasusunan supaya nombor positif dikelilingi oleh nombor negatif. Jika terdapat lebih positif dan Nombor negatif akan diisih pada penghujung tatasusunan.

Mari kita lihat situasi input dan output yang berbeza −

Input − int arr[] = {-1, -2, -3, 1, 2, 3}

Output −: - Array sebelum mengisih -2 -3 1 2 3 Menyusun semula tatasusunan supaya item positif dan negatif silih berganti dan tidak memerlukan ruang tambahan ialah: -1 1 -2 2 -3 3.

Penjelasan: Diberi tatasusunan integer bersaiz 6 yang mengandungi unsur positif dan negatif. Sekarang kita akan menyusun semula tatasusunan supaya semua elemen positif muncul sebelum unsur negatif tanpa memerlukan ruang tambahan Dikelilingi oleh unsur negatif dan semua unsur tambahan, -1 1 -2 2 -3 3 akan ditambahkan pada penghujung tatasusunan akhir, yang merupakan hasil akhir.

Input - int arr[] = {-1, -2, -3, 1, 2, 3, 5, 5, -5, 3, 1, 1};

Output - sebelum menyusun Array : -1 -2 -3 1 2 3 5 5 -5 3 1 1 Kerumitan masa untuk menyusun semula tatasusunan dengan menyelang-seli sebutan positif dan negatif tanpa menggunakan ruang tambahan ialah O(1): -1 1 -2 2 -3 3 -5 5 5 3 1 1

Penjelasan - Kami memberikan integer An tatasusunan saiz 12 yang mengandungi unsur positif dan negatif. Sekarang kita akan menyusun semula tatasusunan sedemikian rupa sehingga semua elemen positif dikelilingi oleh unsur negatif dan menambah semua elemen tambahan ke penghujung tatasusunan iaitu -1 1 -2 2 -3 3 -5 5 5 3 1 1 akan menjadi keputusan akhir.

Kaedah yang digunakan dalam atur cara di bawah adalah seperti berikut

• Masukkan tatasusunan jenis integer dan kira saiz tatasusunan.

• Gunakan gelung FOR untuk mencetak tatasusunan sebelum melakukan operasi susun semula.

• Penyusunan semula fungsi panggilan(arr, saiz) dengan menghantar saiz tatasusunan dan tatasusunan sebagai parameter.

• Di dalam fungsi Penyusunan Semula(arr, saiz)

  • isytiharkan pembolehubah integer 'ptr' dan mulakannya kepada -1.

  • Gelung dari i ke 0 sehingga i kurang daripada saiz. Di dalam gelung, semak jika ptr lebih besar daripada 0, kemudian semak jika arr[i] lebih besar daripada 0 dan arr[ptr] kurang daripada 0 atau arr[i] kurang daripada 0 dan arr[ptr] lebih besar daripada 0 , kemudian panggil fungsi move_array(arr, size, ptr, i), dan semak jika i - ptr lebih besar daripada 2, kemudian tetapkan ptr kepada ptr + 2. Jika tidak, tetapkan ptr kepada -1.

  • Semak sama ada ptr bersamaan dengan -1, kemudian semak arr[i] lebih besar daripada 0 dan !(i & 0x01) atau (arr[i] kurang daripada 0) dan (i & 0x01), kemudian tetapkan ptr kepada i.

• Di dalam fungsi move_array(int arr[], saiz int, int ptr, int temp)

  • isytiharkan pembolehubah jenis aksara bernama 'ch' dan tetapkannya kepada arr[temp] .

  • Gelung dari i ke suhu sehingga i lebih besar daripada ptr. Di dalam gelung, tetapkan arr[i] kepada arr[i - 1].

  • Tetapkan arr[ptr] kepada ch.

Contoh

#include <iostream>
#include <assert.h>
using namespace std;
void move_array(int arr[], int size, int ptr, int temp){
   char ch = arr[temp];
   for(int i = temp; i > ptr; i--){
      arr[i] = arr[i - 1];
   }
   arr[ptr] = ch;
}
void Rearrangement(int arr[], int size){
   int ptr = -1;
   for(int i = 0; i < size; i++){
      if (ptr >= 0){
         if(((arr[i] >= 0) && (arr[ptr] < 0)) || ((arr[i] < 0) && (arr[ptr] >= 0))){
            move_array(arr, size, ptr, i);
            if(i - ptr >= 2){
               ptr = ptr + 2;
            }
            else{
               ptr = -1;
            }
         }
      }
      if(ptr == -1){
         if (((arr[i] >= 0) && (!(i & 0x01))) || ((arr[i] < 0) && (i & 0x01))){
            ptr = i;
         }
      }
   }
}
int main(){
   //input an array
   int arr[] = {-1, -2, -3, 1, 2, 3};
   int size = sizeof(arr) / sizeof(arr[0]);
   //print the original Array
   cout<<"Array before Arrangement: ";
   for (int i = 0; i < size; i++){
      cout << arr[i] << " ";
   }
   //calling the function to rearrange the array
   Rearrangement(arr, size);
   //print the array after rearranging the values
   cout<<"\nRearrangement of an array in alternating positive & negative items with O(1) extra space is: ";
   for(int i = 0; i < size; i++){
      cout<< arr[i] << " ";
   }
   return 0;
}

Output

Jika kita menjalankan kod di atas, ia akan menghasilkan output berikut

Array before Arrangement: -1 -2 -3 1 2 3
Rearrangement of an array in alternating positive & negative items with O(1) extra space is: -1 1 -2 2 -3 3

Atas ialah kandungan terperinci Dalam C++, gunakan ruang tambahan O(1) untuk menyusun semula tatasusunan supaya item positif dan negatif silih berganti. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!