Conteo de elementos más grandes en el lado derecho de cada elemento en una array

Dada una array arr[] que consta de N enteros, la tarea es contar el número de elementos mayores en el lado derecho de cada elemento de la array.

Ejemplos:

Entrada: arr[] = {3, 7, 1, 5, 9, 2} Salida: {3, 1, 3, 1, 0, 0} Explicación: Para arr[0], los elementos mayores que él a la derecha son {7, 5, 9}. Para arr[1], el único elemento mayor que él a la derecha es {9}. Para arr[2], los elementos mayores que él a la derecha son {5, 9, 2}. Para arr[3], el único elemento mayor que él a la derecha es {9}. Para arr[4] y arr[5], no existen elementos mayores a la derecha.

Entrada: arr[] = {5, 4, 3, 2} Salida: {0, 0, 0, 0}

Enfoque ingenuo: el enfoque más simple es iterar todos los elementos de la array utilizando dos bucles y, para cada elemento de la array, contar la cantidad de elementos mayores que él en su lado derecho y luego imprimirlo. Complejidad de Tiempo: O(N ² ) Espacio Auxiliar: O(1)

Enfoque eficiente: el problema se puede resolver utilizando el concepto de Merge Sort en orden descendente. Siga los pasos que se indican a continuación para resolver el problema:

• Inicialice una array count[] donde count[i] almacene el recuento respectivo de elementos mayores a la derecha para cada arr[i]
• Tome los índices i y j y compare los elementos en una array.
• Si el elemento de índice más alto es mayor que el elemento de índice más bajo, entonces, todo el elemento de índice más alto será mayor que todos los elementos después de ese índice más bajo.
• Dado que la parte izquierda ya está ordenada, agregue el recuento de elementos después del elemento de índice inferior a la array count[] para el índice inferior.
• Repita los pasos anteriores hasta que se ordene toda la array.
• Finalmente imprima los valores de la array count[] .

A continuación se muestra la implementación del enfoque anterior: 

// Java program for the above approach
 
import java.util.*;
 
public class GFG {
 
    // Stores the index & value pairs
    static class Item {
 
        int val;
        int index;
 
        public Item(int val, int index)
        {
            this.val = val;
            this.index = index;
        }
    }
 
    // Function to count the number of
    // greater elements on the right
    // of every array element
    public static ArrayList<Integer>
    countLarge(int[] a)
    {
        // Length of the array
        int len = a.length;
 
        // Stores the index-value pairs
        Item[] items = new Item[len];
 
        for (int i = 0; i < len; i++) {
            items[i] = new Item(a[i], i);
        }
 
        // Stores the count of greater
        // elements on right
        int[] count = new int[len];
 
        // Perform MergeSort operation
        mergeSort(items, 0, len - 1,
                  count);
 
        ArrayList<Integer> res
            = new ArrayList<>();
 
        for (int i : count) {
            res.add(i);
        }
 
        return res;
    }
 
    // Function to sort the array
    // using Merge Sort
    public static void mergeSort(
        Item[] items, int low int high,
        int[] count)
    {
 
        // Base Case
        if (low >= high) {
            return;
        }
 
        // Find Mid
        int mid = low + (high - low) / 2;
 
        mergeSort(items, low, mid,
                  count);
        mergeSort(items, mid + 1,
                  high, count);
 
        // Merging step
        merge(items, low, mid,
              mid + 1, high, count);
    }
 
    // Utility function to merge sorted
    // subarrays and find the count of
    // greater elements on the right
    public static void merge(
        Item[] items, int low, int lowEnd,
        int high, int highEnd, int[] count)
    {
        int m = highEnd - low + 1; // mid
 
        Item[] sorted = new Item[m];
 
        int rightCounter = 0;
        int lowInd = low, highInd = high;
        int index = 0;
 
        // Loop to store the count of
        // larger elements on right side
        // when both array have elements
        while (lowInd <= lowEnd
               && highInd <= highEnd) {
 
            if (items[lowInd].val
                < items[highInd].val) {
                rightCounter++;
                sorted[index++]
                    = items[highInd++];
            }
            else {
                count[items[lowInd].index] += rightCounter;
                sorted[index++] = items[lowInd++];
            }
        }
 
        // Loop to store the count of
        // larger elements in right side
        // when only left array have
        // some element
        while (lowInd <= lowEnd) {
 
            count[items[lowInd].index] += rightCounter;
            sorted[index++] = items[lowInd++];
        }
 
        // Loop to store the count of
        // larger elements in right side
        // when only right array have
        // some element
        while (highInd <= highEnd) {
 
            sorted[index++] = items[highInd++];
        }
 
        System.arraycopy(sorted, 0, items,
                         low, m);
    }
 
    // Utility function that prints
    // the count of greater elements
    // on the right
    public static void
    printArray(ArrayList<Integer> countList)
    {
 
        for (Integer i : countList)
            System.out.print(i + " ");
 
        System.out.println();
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        // Given array
        int arr[] = { 3, 7, 1, 5, 9, 2 };
        int n = arr.length;
 
        // Function Call
        ArrayList<Integer> countList
            = countLarge(arr);
 
        printArray(countList);
    }
}

Complejidad de tiempo: O(N*log N) Espacio auxiliar: O(N)

Otro enfoque: podemos usar la búsqueda binaria para resolver esto. La idea es crear una lista ordenada de entrada y luego, para cada elemento de entrada, primero eliminamos ese elemento de la lista ordenada y luego aplicamos la búsqueda binaria modificada para encontrar el elemento justo mayor que el elemento actual y luego la cantidad de elementos grandes. será la diferencia entre el índice encontrado y la longitud de la lista ordenada. 

using System;
using System.Collections.Generic;
 
public class GFG{
    static public void Main (){
        //Code
          var arr = new List<int>(){3, 7, 1, 5, 9, 2};
        var res = CountLarge(arr);
        PrintArray(res);
    }
    public static List<int> CountLarge(List<int> list)
    {
        var sortedList = new List<int>(list);
        sortedList.Sort();
        for(int i=0;i<list.Count;i++){
            DeleteItemFromSortedList(sortedList, list[i]);
            list[i] = CountLargeNumbers(list[i], sortedList);
        }
        return list;
    }
    public static int CountLargeNumbers(int item, List<int> list){
        int l=0,r=list.Count-1,mid;
        while(l<r){
            mid = l + (r-l)/2;
            if(list[mid] > item)
                r = mid;
            else
                l = mid + 1;
        }
        if(l==r && item > list[l])
            return 0;
        return list.Count-l;
    }
    public static void DeleteItemFromSortedList(List<int> list, int item){
        var index = BinarySearch(list, item);
        list.RemoveAt(index);
    }
    public static int BinarySearch(List<int> list, int item){
        int l=0,r=list.Count-1,mid;
        while(l<=r){
            mid = l + (r-l)/2;
            if(list[mid] == item)
                return mid;
            else if(list[mid] < item)
                l = mid + 1;
            else
                r = mid - 1;
        }
        return -1;
    }
    public static void PrintArray(List<int> list)
    {
        foreach(var item in list)
            Console.Write(item + " ");
    }
}

5 2 6 3 1 3 0 1 0 

Complejidad de tiempo: O(N*log N) Espacio auxiliar: O(N)