Đếm số phần tử lớn hơn bên phải (Surpasser Count) trong mảng C++

Cho mảng A. Surpasser của phần tử A[i] là số phần tử lớn hơn A[i] nằm ở bên phải (chỉ số > i). Ví dụ A = {2, 7, 5, 3, 0, 8, 1} → surpassers = {4, 1, 1, 1, 2, 0, 0}.

Giải pháp đơn giản: 2 vòng lặp lồng, đếm phần tử lớn hơn bên phải cho mỗi i.

Ví dụ

#include <iostream>
using namespace std;

void gerSurpassers(int arr[], int surpassers[], int n){
    for(int i = 0; i<n; i++){
        int count = 0;
        for(int j = i+1; j<n; j++){
            if(arr[j] > arr[i])
                count++;
        }
        surpassers[i] = count;
    }
}

void displayArray(int arr[], int n){
    for(int i = 0; i<n; i++)
        cout << arr[i] << " ";
    cout << "\n";
}

int main() {
    int arr[] = {2, 7, 5, 3, 0, 8, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    int surpassers[n];
    cout << "Elements :"; displayArray(arr, n);
    gerSurpassers(arr, surpassers, n);
    cout << "Surpassers:"; displayArray(surpassers, n);
}

Kết quả

Elements :2 7 5 3 0 8 1 Surpassers:4 1 1 1 2 0 0