Susun semula tatasusunan supaya arr menjadi arr] dan hanya gunakan ruang tambahan O(1), dilaksanakan dalam C++

Kami mendapat tatasusunan jenis integer positif, contohnya, arr[] sebarang saiz tertentu, supaya nilai elemen dalam tatasusunan hendaklah lebih besar daripada 0 tetapi kurang daripada saiz tatasusunan. Tugasnya ialah menyusun semula Tatasusunan yang hanya menukar arr[i] kepada arr[arr[i]] dalam ruang O(1) yang diberikan dan mencetak hasil akhir.

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

Input− int arr[] = {0 5 4 2 }

Output− Tatasusunan sebelum mengisih: 0 3 2 1 5 4 Susun semula tatasusunan supaya arr[i] menjadi arr[arr[i]], dengan O(1) ruang tambahan: 0 1 2 3 4 5

Penjelasan#🎜🎜 #− Kami diberi tatasusunan integer bersaiz 6, dan semua elemen dalam tatasusunan mempunyai nilai kurang daripada 6. Sekarang, kita akan menyusun semula tatasusunan supaya arr[arr[0] ialah 0, arr[arr[1]] ialah 1, arr[arr [2]] ialah 2, arr[arr[3]] ialah 3, arr[ arr[4]] ialah 4, arr[arr[5]] ialah 5. Oleh itu, tatasusunan akhir selepas penyusunan semula ialah 0 1 2 3 4 5. 🎜#Output

− Tatasusunan sebelum mengisih: 1 0 Susun semula tatasusunan supaya arr[i] menjadi arr[arr[i]], dengan ruang tambahan O(1) ialah: 0 1

Penjelasan

- Kami mendapat An tatasusunan saiz integer 2 dengan semua elemen dalam tatasusunan mempunyai nilai kurang daripada 2. Sekarang, kita akan menyusun semula tatasusunan supaya arr[arr[0] ialah 1 dan arr[arr[1]] ialah 0. Oleh itu, tatasusunan akhir selepas penyusunan semula ialah 0 1.

Input

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

−🎜#−🎜 Tatasusunan sebelum mengisih: 1 0 2 3 Susun semula tatasusunan supaya arr[i] menjadi arr[arr[i]], dengan O(1) ruang tambahan: 0 1 2 3

Penjelasan - Kami diberikan tatasusunan integer bersaiz 4, dan semua elemen dalam tatasusunan mempunyai nilai kurang daripada 4. Sekarang, kita akan menyusun semula tatasusunan supaya arr[arr[0] ialah 0, arr[arr[1]] ialah 1, arr[arr[2] ]] ialah 2, dan arr[arr[3]] ialah 3. Oleh itu, tatasusunan akhir selepas penyusunan semula ialah 0 1 2 3.

Kaedah yang digunakan dalam atur cara berikut adalah seperti berikut

Masukkan tatasusunan elemen integer dan kira saiz tatasusunan# 🎜🎜## 🎜🎜#Cetak tatasusunan sebelum susunan dan panggil fungsi Susunan Semula (arr, saiz)

Fungsi penyusunan semula dalaman) (arr, saiz)
Mulakan gelung UNTUK dari i ke 0 sehingga i kurang daripada saiz. Di dalam gelung, tetapkan temp kepada arr[arr[i]] % size dan arr[i] += temp * size.
Mulakan gelung UNTUK dari i ke 0 sehingga i kurang daripada saiz. Dalam gelung, tetapkan arr[i] = arr[i] / saiz

• • untuk mencetak hasilnya.

  • Contoh

    #include <bits/stdc++.h>
    using namespace std;
    void Rearrangement(int arr[], int size){
       for(int i=0; i < size; i++){
          int temp = arr[arr[i]] % size;
          arr[i] += temp * size;
       }
       for(int i = 0; i < size; i++){
          arr[i] = arr[i] / size;
       }
    }
    int main(){
       //input an array
       int arr[] = {0, 3, 2, 1, 5, 4};
       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 so that arr[i] becomes arr[arr[i]] 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 menjana kod output berikut #

Array before Arrangement: 0 3 2 1 5 4
Rearrangement of an array so that arr[i] becomes arr[arr[i]] with O(1) extra space is: 0 1 2 3 4 5

Atas ialah kandungan terperinci Susun semula tatasusunan supaya arr menjadi arr] dan hanya gunakan ruang tambahan O(1), dilaksanakan dalam C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!