Dalam C++, susun semula nombor positif dan negatif dalam kerumitan masa O(n) dan ruang tambahan O(1).

Kami mendapat tatasusunan jenis integer yang mengandungi nombor positif dan negatif, katakan, arr[] sebarang saiz tertentu. Tugasnya adalah untuk menyusun semula tatasusunan supaya semua nombor positif dan negatif harus berada dalam kedudukan berselang-seli dan jika terdapat nombor tambahan positif atau negatif elemen dan ia akan diletakkan di hujung tatasusunan.

Mari kita lihat pelbagai senario input dan output untuk situasi ini -

input − int arr[] = {4, 2, -1, -1, 6, -3}

output− dalam positif nombor negatif dalam masa O(n) dan ruang tambahan masa O(1) ialah: 2 - 1 6 -1 4 -3

Penjelasan− Kami mendapat tatasusunan integer saiz 6 yang mengandungi unsur Positif dan negatif. Sekarang kita akan menyusun semula tatasusunan supaya semua elemen positif berjumlah Elemen negatif berada pada kedudukan bersilih ganti dan semua elemen tambahan akan ditambahkan pada penghujung tatasusunan iaitu 2 -1 6 -1 4 -3 akan menjadi hasil akhir

input

input

kuat>− int arr [] = {- 1, -2, -3, 1, 2, 3, 5, 5, -5, 3, 1, 1}

output strong>− dalam masa O(n) dan O(1) tambahan ruang dan nombor negatif disusun semula sebagai: 2 - 2 3 -5 5 -3 5 -1 1 3 1 1

Penjelasan - Kami mendapat tatasusunan integer bersaiz 12 yang mengandungi unsur positif dan negatif. Sekarang kita akan menyusun semula tatasusunan supaya semua elemen positif dan negatif berada dalam kedudukan berselang-seli dan semua elemen tambahan akan ditambah pada penghujung tatasusunan iaitu 2 -2 3 -5 5 -3 5 -1 1 3 1 1 untuk perlawanan akhir Result

Kaedah yang digunakan dalam atur cara di bawah adalah seperti berikut

• Masukkan elemen input tatasusunan integer dan kira saiz tatasusunan.

• Cetak tatasusunan sebelum melakukan operasi susun semula menggunakan gelung FOR.

• Panggil fungsi Susunan Semula(arr, saiz) dengan menghantar tatasusunan dan saiz tatasusunan sebagai argumen.

• fungsi Penyusunan semula(arr, saiz) secara dalaman

  • mengisytiharkan pembolehubah integer sementara, iaitu, temp ialah -1, nombor positif ialah temp + 1, dan nombor negatif ialah 0.

  • Mulakan gelung dari i ke 0 sehingga i kurang daripada saiz tatasusunan. Di dalam gelung, semak JIKA arr[i] kurang daripada 0, kemudian naikkan suhu sebanyak 1 dan panggil kaedah terbina dalam C++ STL, iaitu swap(arr[temp], arr[i]) dan lulus arr[temp ] dan arr[i] sebagai parameter.

  • Mulakan gelung, MANAKALA nombor positif kurang daripada saiz tatasusunan DAN nombor negatif kurang daripada nombor positif DAN arr[nombor negatif] kurang daripada 0. Dalam gelung, panggilan ditukar dengan menghantar arr[negatif] dan arr[positif] sebagai argumen. Tambahkan 1 pada nombor positif dan tetapkan negatif + 2 kepada nombor negatif.

• Cetak hasilnya.

Contoh

#include <bits/stdc++.h>
using namespace std;
void Rearrangement(int arr[], int size){
   int temp = -1;
   for(int i = 0; i < size; i++){
      if (arr[i] < 0){
         temp++;
         swap(arr[temp], arr[i]);
      }
   }
   int positive = temp + 1;
   int negative = 0;
   while(positive < size && negative < positive && arr[negative] < 0){
      swap(arr[negative], arr[positive]);
      positive++;
      negative = negative + 2;
   }
}
int main(){
   int arr[] = {4, 2, -1, -1, 6, -3};
   int size = sizeof(arr)/sizeof(arr[0]);
   //calling the function to rearrange the array
   Rearrangement(arr, size);
   //print the array after rearranging the values
   cout<<"Rearrangement of positive and negative numbers in O(n) time and 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

Rearrangement of positive and negative numbers in O(n) time and O(1) extra space is: 2 -1 6 -1 4 -3

Atas ialah kandungan terperinci Dalam C++, susun semula nombor positif dan negatif dalam kerumitan masa O(n) dan ruang tambahan O(1).. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!