Xếp hạng các phần tử trong mảng bằng C++

Trong bài toán này, chúng ta cần xếp hạng tất cả các phần tử của một mảng: số nhỏ nhất có hạng thấp nhất, số lớn nhất có hạng cao nhất. Nếu một giá trị xuất hiện nhiều lần, hạng của chúng là trung bình các vị trí mà chúng chiếm. Ví dụ:

Input : 20 30 10 Output : 2.0 3.0 1.0 Input : 10 12 15 12 10 25 12 Output : 1.5, 4.0, 6.0, 4.0, 1.5, 7.0, 4.0 Giải thích: Giá trị 10 xuất hiện 2 lần, chiếm hạng 1 và 2 → hạng trung bình = 1.5. Input : 1, 2, 5, 2, 1, 60, 3 Output : 1.5, 3.5, 6.0, 3.5, 1.5, 7.0, 5.0

Các cách tiếp cận

Có hai cách giải quyết: cách vét cạn (Brute Force) và cách hiệu quả (Efficient).

Cách vét cạn (Brute Force)

Với mỗi phần tử, duyệt toàn mảng để đếm số phần tử nhỏ hơn nó (r) và số phần tử bằng nó (s). Hạng = r + (s - 1) / 2.0.

Ví dụ

#include <bits/stdc++.h>
using namespace std;

int main() {
    int arr[] = {1, 2, 5, 2, 1, 25, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    float rank[n] = {0};
    for (int i = 0; i < n; i++) {
        int r = 1, s = 1;
        for (int j = 0; j < n; j++) {
            if (j != i && arr[j] < arr[i]) r++;
            if (j != i && arr[j] == arr[i]) s++;
        }
        rank[i] = r + (float)(s - 1) / 2.0;
    }
    for (int i = 0; i < n; i++) cout << rank[i] << ' ';
    return 0;
}

Kết quả

1.5 4 6 4 1.5 7 4

Độ phức tạp O(N²) — không phù hợp với dữ liệu lớn.

Cách hiệu quả (Efficient Approach)

Sắp xếp mảng, sau đó duyệt một lần để gán hạng trung bình cho các giá trị trùng nhau, dùng map lưu kết quả.

Ví dụ

#include <bits/stdc++.h>
using namespace std;

int main() {
    int arr[] = {1, 2, 5, 2, 1, 60, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    float rank[n] = {0};
    int old[n];
    for (int i = 0; i < n; i++) old[i] = arr[i];
    sort(arr, arr + n);
    int prev = arr[0];
    int r = 1, s = 0, tot = 0;
    map<int, float> rrank;
    for (int i = 0; i < n; i++) {
        if (prev == arr[i]) {
            s++;
            tot += r;
        } else {
            float now = (float)tot / s;
            rrank[prev] = now;
            prev = arr[i];
            tot = r;
            s = 1;
        }
        r++;
    }
    rrank[arr[n-1]] = (float)tot / s;
    for (int i = 0; i < n; i++) cout << rrank[old[i]] << " ";
    return 0;
}

Kết quả

1.5 3.5 6 3.5 1.5 7 5

Giải thích

Sắp xếp mảng → các giá trị giống nhau nằm cạnh nhau. Duyệt một lần, cộng dồn hạng (tot) và đếm tần suất (s). Khi gặp giá trị mới, tính hạng trung bình = tot / s lưu vào map. Cuối cùng tra cứu hạng cho mảng gốc.

Kết luận

Đã giải quyết bài toán xếp hạng phần tử mảng bằng hai cách: vét cạn O(N²) và hiệu quả O(N log N) nhờ sắp xếp + map. Code C++ mẫu có thể chuyển sang C, Java, Python dễ dàng.