Recuento de elementos mayores para cada elemento en el Array

Dada una array arr de enteros de tamaño N , la tarea es encontrar, para cada elemento, el número de elementos que son mayores que él.
Ejemplos: 
 

Entrada: arr[] = {4, 6, 2, 1, 8, 7} 
Salida: {3, 2, 4, 5, 0, 1}
Entrada: arr[] = {2, 3, 4, 5, 6 , 7, 8} 
Salida: {6, 5, 4, 3, 2, 1, 0} 
 

Enfoque: almacene las frecuencias de cada elemento de la array utilizando un mapa . Iterar el Mapa a la inversa y almacenar la suma de la frecuencia de todos los elementos recorridos previamente (es decir, elementos mayores que él) para cada elemento.
El siguiente código es la implementación del enfoque anterior:
 

// C++ implementation of the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
void countOfGreaterElements(int arr[], int n)
{
    // Store the frequency of the
    // array elements
    map<int, int> mp;
    for (int i = 0; i < n; i++) {
        mp[arr[i]]++;
    }
 
    int x = 0;
    // Store the sum of frequency of elements
    // greater than the current element
    for (auto it = mp.rbegin(); it != mp.rend(); it++) {
        int temp = it->second;
        mp[it->first] = x;
        x += temp;
    }
 
    for (int i = 0; i < n; i++)
        cout << mp[arr[i]] << " ";
}
 
// Driver code
int main()
{
 
    int arr[] = { 7, 9, 5, 2, 1, 3, 4, 8, 6 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    countOfGreaterElements(arr, n);
 
    return 0;
}

// Java implementation of the above approach
import java.util.*;
 
class GfG {
    public static void countOfGreaterElements(int arr[])
    {
        int n = arr.length;
 
        TreeMap<Integer, Integer> mp = new TreeMap<Integer, Integer>(Collections.reverseOrder());
 
        // Store the frequency of the
        // array elements
        for (int i = 0; i < n; i++) {
            mp.put(arr[i], mp.getOrDefault(arr[i], 0) + 1);
        }
 
        // Store the sum of frequency of elements
        // greater than the current element
        int x = 0;
        for (Map.Entry<Integer, Integer> e : mp.entrySet()) {
            Integer temp = e.getValue();
            mp.put(e.getKey(), x);
            x += temp;
        }
 
        for (int i = 0; i < n; i++)
            System.out.print(mp.get(arr[i]) + " ");
    }
 
    public static void main(String args[])
    {
        int arr[] = { 7, 9, 5, 2, 1, 3, 4, 8, 6 };
        countOfGreaterElements(arr);
    }
}

# Python 3 implementation of the above approach
 
def countOfGreaterElements(arr, n):
    # Store the frequency of the
    # array elements
    mp = {i:0 for i in range(1000)}
    for i in range(n):
        mp[arr[i]] += 1
 
    x = 0
    # Store the sum of frequency of elements
    # greater than the current element
    p = []
    q = []
    m = []
    for key, value in mp.items():
        m.append([key, value])
    m = m[::-1]
     
    for p in m:
        temp = p[1]
        mp[p[0]] = x
        x += temp
 
    for i in range(n):
        print(mp[arr[i]], end = " ")
 
# Driver code
if __name__ == '__main__':
    arr = [7, 9, 5, 2, 1, 3, 4, 8, 6]
    n = len(arr)
 
    countOfGreaterElements(arr, n)
 
# This code is contributed by Surendra_Gangwar

2 0 4 7 8 6 5 1 3

Complejidad de tiempo: O(N log(N))

Espacio Auxiliar: O(N)