Cho mảng, chuyển thành dạng rút gọn: các phần tử trở thành 0..n-1 theo thứ tự lớn nhỏ.
Input: {10, 20, 15, 12, 11, 50} Output: 0 4 3 2 1 5
Giải pháp: Tạo vector pair (giá trị, index). Sắp xếp theo giá trị. Gán rank vào mảng gốc theo index.
Chương trình minh họa
#include <bits/stdc++.h>
using namespace std;
void convert(int arr[], int n){
vector<pair<int, int> > v;
for (int i = 0; i < n; i++) v.push_back({arr[i], i});
sort(v.begin(), v.end());
for (int i = 0; i < n; i++) arr[v[i].second] = i;
}
void print_array(int arr[], int n){
for (int i = 0; i < n; i++) cout << arr[i] << " ";
}
int main(){
int arr[] = {10, 20, 15, 12, 11, 50};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "Mảng gốc:\n"; print_array(arr, n);
convert(arr, n);
cout << "\nMảng rút gọn:\n"; print_array(arr, n);
return 0;
}
Kết quả
Mảng gốc: 10 20 15 12 11 50 Mảng rút gọn: 0 4 3 2 1 5