Cuente las posiciones de modo que todos los elementos anteriores sean mayores

Dado un arreglo A[] , la tarea es encontrar el número de posiciones i en el arreglo tal que todos los elementos antes de A[i] sean mayores que A[i].
Nota : el primer elemento siempre se cuenta porque no hay ningún otro elemento antes.
Ejemplos: 
 

Input: N = 4, A[] = {2, 1, 3, 5} 
Output: 2
The valid positions are 1, 2.

Input : N = 3, A[] = {7, 6, 5}
Output: 3
All three positions are valid positions.

La idea es calcular el elemento mínimo cada vez que se atraviesa la array. Eso es: 
 

  • Inicialice el primer elemento como el elemento mínimo.
  • Cada vez que llega un nuevo elemento, verifique si este es el nuevo mínimo, si es así, incremente el número de posiciones válidas y también inicialice el mínimo al nuevo mínimo.

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

CPP

// C++ Program to count positions such that all
// elements before it are greater
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to count positions such that all
// elements before it are greater
int getPositionCount(int a[], int n)
{  
    // Count is initially 1 for the first element
    int count = 1;
     
    // Initial Minimum
    int min = a[0];
     
    // Traverse the array
    for(int i=1; i<n; i++)
    {  
        // If current element is new minimum
        if(a[i] <= min)
        {
            // Update minimum
            min = a[i];
             
            // Increment count
            count++;
        }
    }
     
    return count;
}
 
// Driver Code
int main()
{
    int a[] = { 5, 4, 6, 1, 3, 1 };
    int n = sizeof(a) / sizeof(a[0]);
 
    cout<<getPositionCount(a, n);
     
    return 0;
}

Java

// Java Program to count positions such that all
// elements before it are greater
class GFG
{
 
// Function to count positions such that all
// elements before it are greater
static int getPositionCount(int a[], int n)
{
    // Count is initially 1 for the first element
    int count = 1;
     
    // Initial Minimum
    int min = a[0];
     
    // Traverse the array
    for(int i = 1; i < n; i++)
    {
        // If current element is new minimum
        if(a[i] <= min)
        {
            // Update minimum
            min = a[i];
             
            // Increment count
            count++;
        }
    }
     
    return count;
}
 
// Driver Code
public static void main(String[] args)
{
    int a[] = { 5, 4, 6, 1, 3, 1 };
    int n = a.length;
 
    System.out.print(getPositionCount(a, n));
}
}
 
// This code is contributed by PrinciRaj1992

Python3

# Python3 Program to count positions such that all
# elements before it are greater
 
# Function to count positions such that all
# elements before it are greater
def getPositionCount(a, n) :
 
    # Count is initially 1 for the first element
    count = 1;
     
    # Initial Minimum
    min = a[0];
     
    # Traverse the array
    for i in range(1, n) :
     
        # If current element is new minimum
        if(a[i] <= min) :
         
            # Update minimum
            min = a[i];
             
            # Increment count
            count += 1;
     
    return count;
 
# Driver Code
if __name__ == "__main__" :
 
    a = [ 5, 4, 6, 1, 3, 1 ];
    n = len(a);
     
    print(getPositionCount(a, n));
     
# This code is contributed by AnkitRai01

C#

// C# Program to count positions such that all
// elements before it are greater
using System;
 
class GFG
{
     
    // Function to count positions such that all
    // elements before it are greater
    static int getPositionCount(int []a, int n)
    {
        // Count is initially 1 for the first element
        int count = 1;
         
        // Initial Minimum
        int min = a[0];
         
        // Traverse the array
        for(int i = 1; i < n; i++)
        {
            // If current element is new minimum
            if(a[i] <= min)
            {
                // Update minimum
                min = a[i];
                 
                // Increment count
                count++;
            }
        }
         
        return count;
    }
     
    // Driver Code
    public static void Main()
    {
        int []a = { 5, 4, 6, 1, 3, 1 };
        int n = a.Length;
     
        Console.WriteLine(getPositionCount(a, n));
    }
}
 
// This code is contributed by AnkitRai01

Javascript

<script>
 
// Javascript Program to count positions such that all
// elements before it are greater
 
// Function to count positions such that all
// elements before it are greater
function getPositionCount(a, n)
{  
    // Count is initially 1 for the first element
    var count = 1;
     
    // Initial Minimum
    var min = a[0];
     
    // Traverse the array
    for(var i = 1; i < n; i++)
    {  
        // If current element is new minimum
        if(a[i] <= min)
        {
            // Update minimum
            min = a[i];
             
            // Increment count
            count++;
        }
    }
     
    return count;
}
 
// Driver Code
var a = [5, 4, 6, 1, 3, 1];
var n = a.length;
document.write( getPositionCount(a, n));
 
// This code is contributed by itsok.
</script>
Producción: 

4

 

Complejidad de tiempo: O(N)
 

Publicación traducida automáticamente

Artículo escrito por souradeep y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *