Clasificación de todos los elementos en un Stream en orden descendente cuando llegan

Posted on by Rudeus Greyrat

Dada una secuencia de números como arr , la tarea es encontrar el rango de cada elemento en la secuencia en orden descendente cuando llegan.  

El rango se define como el número total de elementos que es mayor que el elemento que llega, donde el rango 1 define el valor máximo en la secuencia. Cada valor en la array es único.

Ejemplos: 

Entrada: arr = [88, 14, 69, 30, 29, 89] 
Salida: 1 2 2 3 4 1 
Explicación: 
Primero llega 88, por lo que su rango es 1. 
Cuando llega 14, 14 es menor que 88, por lo que su rango es 2. 
cuando llega 69, 69 es menor que 88 y mayor que 14 por lo que su rango es 2. 
cuando llega 30, 30 es menor que 88 y 69 por lo que su rango es 3. 
cuando llega 29, 29 es menor que 88, 69, 30 que 29 por lo que su rango es 4. 
cuando llega 89, 89 es mayor que todos los valores por lo que su rango es 1. 
El rango de los elementos de la array 1 2 2 3 4 1
Entrada: arr = [100, 110, 80, 85, 88, 89] 
Salida: 1 1 3 3 3 3 
Explicación: 
Los primeros 100 llegan por lo que su rango es 1. 
cuando llegan 110, 110 es mayor que 100 entonces su rango es 1. 
cuando llegan 80, 80 es menor que 110 y 100 entonces su rango es 3. 
cuando llegan 85, 85 es menor que 110 y 100 entonces su rango es 3. 
cuando 88 llegan, 88 es menor que 110 y 100 por lo que su rango es 3. 
cuando llegan 89, 89 es menor que 110 y 100 por lo que su rango es 3. 
El rango de los elementos de la array 1 1 3 3 3 3 
 

Enfoque ingenuo: 

  1. El primer elemento de la array siempre tendrá rango 1. 
     
  2. Iterar sobre la array, si el elemento es el mayor entre los elementos anteriores, entonces su rango es 1. 
     
  3. Si el elemento no es mayor que los elementos comparados anteriormente. entonces el rango de este elemento será el número de elementos mayores antes que él.
    Por ejemplo, digamos que si es mayor que los 2 elementos anteriores, entonces su rango es 3. 
     

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

C++

// C++ program to rank of all elements
// in a Stream in descending order
// when they arrive
#include <iostream>
using namespace std;
     
    // FindRank function to find rank
        void FindRank(int arr[], int length)
    {
        // Rank of first element is always 1
        cout << "1" <<  " ";
         
        // Iterate over array
        for (int i = 1; i < length; i++)
        {
            // As element let say its rank is 1
            int rank = 1;
     
            // Element is compared
            // with previous elements
            for (int j = 0; j < i; j++)
            {
                // If greater than previous
                // than rank is incremented
                if(arr[j] > arr[i])
                    rank++;
                 
            }
             
            // print rank
            cout <<  rank  << " ";
        }
    }
 
 
 
 
// Driver code
int main() {
     
        // array named arr
        int arr[] = {88, 14, 69, 30, 29, 89};
     
        // length of arr
        int len = sizeof(arr)/sizeof(arr[0]);
     
        FindRank(arr, len);
         
    return 0;
}
 
// This code is contributed by AnkitRai01

Java

// Java program to rank of all elements
// in a Stream in descending order
// when they arrive
import java.util.*;
 
class GFG{
     
    // FindRank function to find rank
    static void FindRank(int arr[], int length)
    {
        // Rank of first element is always 1
        System.out.print("1" + " ");
         
        // Iterate over array
        for (int i = 1; i < arr.length; i++)
        {
            // As element let say its rank is 1
            int rank = 1;
     
            // Element is compared
            // with previous elements
            for (int j = 0; j < i; j++)
            {
                // If greater than previous
                // than rank is incremented
                if(arr[j] > arr[i])
                    rank++;
                 
            }
             
            // print rank
            System.out.print(rank + " ");
        }
    }
 
    // Driver code
    public static void main(String args[]){
         
        // array named arr
        int arr[] = {88, 14, 69, 30, 29, 89};
     
        // length of arr
        int len = arr.length;
     
        FindRank(arr, len);
    }
}
 
// This code is contributed by AbhiThakur

Python3

# Python program to rank of all elements
# in a Stream in descending order
# when they arrive
 
# FindRank function to find rank
def FindRank(arr, length):
     
    # Rank of first element is always 1
    print(1, end =" ")
     
    # Iterate over array
    for i in range(1, length):
         
        # As element let say its rank is 1
        rank = 1
 
        # Element is compared
        # with previous elements
        for j in range(0, i):
             
            # If greater than previous
            # than rank is incremented
            if(arr[j] > arr[i]):
                rank = rank + 1
                 
        # print rank
        print(rank, end =" ")
         
         
# Driver code
if __name__ == '__main__':
     
    # array named arr
    arr = [88, 14, 69, 30, 29, 89]
 
    # length of arr
    length = len(arr)
 
    FindRank(arr, length)

C#

// C# program to rank of all elements
// in a Stream in descending order
// when they arrive
using System;
 
class GFG{
     
    // FindRank function to find rank
    static void FindRank(int[] arr, int length)
    {
        // Rank of first element is always 1
        Console.Write("1" + " ");
         
        // Iterate over array
        for (int i = 1; i < arr.Length; i++)
        {
            // As element let say its rank is 1
            int rank = 1;
     
            // Element is compared
            // with previous elements
            for (int j = 0; j < i; j++)
            {
                // If greater than previous
                // than rank is incremented
                if(arr[j] > arr[i])
                    rank++;
                 
            }
             
            // print rank
            Console.Write(rank + " ");
        }
    }
 
    // Driver code
    public static void Main(){
         
        // array named arr
        int[] arr = {88, 14, 69, 30, 29, 89};
     
        // length of arr
        int len = arr.Length;
     
        FindRank(arr, len);
    }
}
 
// This code is contributed by AbhiThakur

Javascript

<script>
// javascript program to rank of all elements
// in a Stream in descending order
// when they arrive
 
    // FindRank function to find rank
    function FindRank(arr , length) {
        // Rank of first element is always 1
        document.write("1" + " ");
 
        // Iterate over array
        for (i = 1; i < arr.length; i++) {
            // As element let say its rank is 1
            var rank = 1;
 
            // Element is compared
            // with previous elements
            for (j = 0; j < i; j++) {
                // If greater than previous
                // than rank is incremented
                if (arr[j] > arr[i])
                    rank++;
 
            }
 
            // print rank
            document.write(rank + " ");
        }
    }
 
    // Driver code
     
 
        // array named arr
        var arr = [ 88, 14, 69, 30, 29, 89 ];
 
        // length of arr
        var len = arr.length;
 
        FindRank(arr, len);
 
// This code contributed by umadevi9616
</script>
Producción: 

1 2 2 3 4 1

 

Complejidad de tiempo: O(N 2 ) , donde N es la longitud de la array. 
Complejidad del espacio: O(1)
Enfoque eficiente: La idea es utilizar la búsqueda binaria para encontrar el rango del número. Dará la cuenta de números que son mayores que el número dado.
A continuación se muestra la implementación del enfoque anterior:
 

Python3

# Python program to rank of all elements
# in a Stream in descending order
# when they arrive
 
# import of bisect to use bisect.insort()
import bisect
 
# FindRank function to find rank
def FindRank(arr, length):
    # rank list to store values of
    # array in ascending order
    rank = []
 
    first = arr[0]
    rank.append(first)
    # Rank of first element is always 1
    print(1, end =" ")
     
    # Iterate over remaining array
    for i in range(1, length):
        val = arr[i]
         
        # element inserted in the rank list
        # using the binary method
         
        bisect.insort(rank, val)
         
        # To find rank of that element
         
        # length of rank array - index of element
        # in rank array
        eleRank = len(rank)-rank.index(val)
         
        # print of rank of element of array
        print(eleRank, end =" ")
 
# Driver code
if __name__ == '__main__':
     
    # array named arr
    arr = [88, 14, 69, 30, 29, 89]
 
    # lenght of arr
    length = len(arr)
 
    FindRank(arr, length)
Producción: 

1 2 2 3 4 1

 

Complejidad de tiempo: O(N * log N), donde N es la longitud de la array. 
Complejidad del espacio: O(N)
 

Publicación traducida automáticamente

Artículo escrito por Versus 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 *