Chúng ta được cung cấp một mảng kiểu số nguyên dương, giả sử, arr [] có kích thước cho trước bất kỳ sao cho các phần tử trong mảng phải có giá trị lớn hơn 0 nhưng nhỏ hơn kích thước của một mảng. Nhiệm vụ là sắp xếp lại mảng theo cách sao cho arr [i] trở thành arr [arr [i]] chỉ trong khoảng trống O (1) đã cho và in ra kết quả cuối cùng.
Hãy để chúng tôi xem các kịch bản đầu ra đầu vào khác nhau cho việc này -
Đầu vào - int arr [] ={0 3 2 1 5 4}
Đầu ra - Mảng trước Sắp xếp:0 3 2 1 5 4 Sắp xếp lại một mảng để arr [i] trở thành arr [arr [i]] với O (1) khoảng trống thừa là:0 1 2 3 4 5
Giải thích - chúng ta được cung cấp một mảng số nguyên có kích thước là 6 và tất cả các phần tử trong mảng có giá trị nhỏ hơn 6. Bây giờ, chúng ta sẽ sắp xếp lại mảng, tức là arr [arr [0] là 0, arr [arr [1]] là 1, arr [arr [2]] là 2, arr [arr [3]] là 3, arr [arr [4]] là 4 và arr [arr [5]] là 5. Vì vậy, mảng cuối cùng sau khi sắp xếp lại là 0 1 2 3 4 5.
Đầu vào - int arr [] ={1, 0}
Đầu ra - Mảng trước khi sắp xếp:1 0 Sắp xếp lại một mảng để arr [i] trở thành arr [arr [i]] với O (1) khoảng trống thừa là:0 1
Giải thích - chúng ta được cung cấp một mảng số nguyên có kích thước là 2 và tất cả các phần tử trong mảng có giá trị nhỏ hơn 2. Bây giờ, chúng ta sẽ sắp xếp lại mảng, tức là arr [arr [0] là 1 và arr [arr [1]] là 0. Vì vậy , mảng cuối cùng sau khi sắp xếp lại là 0 1.
Đầu vào - int arr [] ={1, 0, 2, 3}
Đầu ra - Mảng trước Sắp xếp:1 0 2 3 Sắp xếp lại một mảng để arr [i] trở thành arr [arr [i]] với O (1) khoảng trống thừa là:0 1 2 3
Giải thích - chúng ta được cung cấp một mảng số nguyên có kích thước là 4 và tất cả các phần tử trong mảng có giá trị nhỏ hơn 4. Bây giờ, chúng ta sẽ sắp xếp lại mảng, tức là arr [arr [0] là 0, arr [arr [1]] là 1, arr [arr [2]] là 2 và arr [arr [3]] là 3. Vì vậy, mảng cuối cùng sau khi sắp xếp lại là 0 1 2 3.
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
-
Nhập một mảng các phần tử kiểu số nguyên và tính kích thước của một mảng
-
In mảng trước khi sắp xếp và gọi hàm Sắp xếp lại (arr, size)
-
Bên trong chức năng Sắp xếp lại (arr, size)
-
Bắt đầu vòng lặp FOR từ i đến 0 cho đến khi tôi nhỏ hơn kích thước. Bên trong vòng lặp, đặt nhiệt độ là arr [arr [i]]% size và arr [i] + =temp * size.
-
Bắt đầu vòng lặp FOR từ i đến 0 cho đến khi tôi nhỏ hơn kích thước. Bên trong vòng lặp, đặt arr [i] =arr [i] / size
-
-
In kết quả.
Ví dụ
#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;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra Kết quả sau
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