Cuente la cantidad de elementos que son mayores que cualquiera de los elementos en el lado derecho de una array

Dada una array Arr[] . La tarea es contar el número de elementos Arr[i] en la array dada de modo que uno o más elementos más pequeños estén presentes en el lado derecho del elemento Arr[i] en la array.

Ejemplos:  

Entrada: Arr[] = { 3, 9, 4, 6, 7, 5 } 
Salida: 3
Los números que cuentan son: 9, 6, 7 
9 – Como todos los números que están presentes después del 9 son menores que 9, 
6 – 5 es elemento más pequeño presente después de él, 
7 – 5 es el elemento más pequeño que está presente después de él.

Entrada: Arr[] = { 3, 2, 1, 2, 3, 4, 5 } 
Salida: 2 
 

Enfoque: 
Comience a atravesar la array desde el último hasta el primer elemento de la array. Mientras se desplaza, mantenga una variable mínima que almacene el elemento mínimo hasta ahora y una variable de contador. Compara la variable min con el elemento actual. Si la variable min es más pequeña que el elemento actual Arr[i] , aumente el contador y si min es mayor que Arr[i] , actualice min .

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

// C++ implementation
#include <bits/stdc++.h>
using namespace std;
 
// function to return the count
int count_greater(int arr[], int n)
{
    int min = INT_MAX;
    int counter = 0;
 
    // Comparing the given element
    // with minimum element till
    // occurred till now.
    for (int i = n - 1; i >= 0; i--) {
        if (arr[i] > min) {
            counter++;
        }
 
        // Updating the min variable
        if (arr[i] <= min) {
            min = arr[i];
        }
    }
 
    return counter;
}
 
// Driver code
int main()
{
    int arr[] = { 3, 2, 1, 2, 3, 4, 5 };
    int n = sizeof(arr) / sizeof(int);
 
    cout << count_greater(arr, n) << endl;
 
    return 0;
}

// Java implementation of the approach
class GFG
{
 
// function to return the count
static int count_greater(int arr[], int n)
{
    int min = Integer.MAX_VALUE;
    int counter = 0;
 
    // Comparing the given element
    // with minimum element till
    // occurred till now.
    for (int i = n - 1; i >= 0; i--)
    {
        if (arr[i] > min)
        {
            counter++;
        }
 
        // Updating the min variable
        if (arr[i] <= min)
        {
            min = arr[i];
        }
    }
    return counter;
}
 
// Driver code
public static void main(String[] args)
{
    int arr[] = { 3, 2, 1, 2, 3, 4, 5 };
    int n = arr.length;
 
    System.out.println(count_greater(arr, n));
}
}
 
// This code is contributed by 29AjayKumar

# Python3 implementation for the above approach
import sys
 
# function to return the count
def count_greater(arr, n) :
 
    min = sys.maxsize;
    counter = 0;
 
    # Comparing the given element
    # with minimum element till
    # occurred till now.
    for i in range(n - 1, -1, -1) :
        if (arr[i] > min) :
            counter += 1;
     
        # Updating the min variable
        if (arr[i] <= min) :
            min = arr[i];
 
    return counter;
 
# Driver code
if __name__ == "__main__" :
 
    arr = [ 3, 2, 1, 2, 3, 4, 5 ];
    n = len(arr);
 
    print(count_greater(arr, n));
     
# This code is contributed by AnkitRai01

// C# implementation of the approach
using System;
 
class GFG
{
     
// function to return the count
static int count_greater(int []arr, int n)
{
    int min = int.MaxValue;
    int counter = 0;
 
    // Comparing the given element
    // with minimum element till
    // occurred till now.
    for (int i = n - 1; i >= 0; i--)
    {
        if (arr[i] > min)
        {
            counter++;
        }
 
        // Updating the min variable
        if (arr[i] <= min)
        {
            min = arr[i];
        }
    }
    return counter;
}
 
// Driver code
static public void Main ()
{
    int []arr = { 3, 2, 1, 2, 3, 4, 5 };
    int n = arr.Length;
     
    Console.Write(count_greater(arr, n));
}
}
 
// This code is contributed by ajit.

<script>
 
// Javascript implementation
 
// Function to return the count
function count_greater(arr, n)
{
    let min = Number.MAX_VALUE;
    let counter = 0;
 
    // Comparing the given element
    // with minimum element till
    // occurred till now.
    for(let i = n - 1; i >= 0; i--)
    {
        if (arr[i] > min)
        {
            counter++;
        }
 
        // Updating the min variable
        if (arr[i] <= min)
        {
            min = arr[i];
        }
    }
    return counter;
}
 
// Driver code
let arr = [ 3, 2, 1, 2, 3, 4, 5 ];
let n = arr.length;
 
document.write(count_greater(arr, n) + "<br>");
 
// This code is contributed by rishavmahato348
 
</script>

2

Complejidad temporal: O(N)
Espacio auxiliar: O(1)