Cuente los elementos de la array con un rango que no exceda K

Dada una array arr[] que consiste en N enteros y un entero K , la tarea es encontrar la cantidad de elementos de la array que tienen rango como máximo K .

Los elementos de array iguales tendrán rangos iguales . Cualquier elemento de array numéricamente más pequeño que su elemento de array inmediato mayor se clasificará en uno más que el número total de elementos de array mayores que él.

Ejemplos:

Entrada: N = 4, arr[] = {100, 50, 50, 25}, K = 3
Salida : 3
Explicación: El rango de los jugadores será {1, 2, 2, 4}.
Hay 3 elementos de array cuyos rangos son menores o iguales a 3.
Por lo tanto, la respuesta es 3.

Entrada: N = 5, arr[] = {2, 2, 3, 4, 5}, K = 4
Salida: 5
Explicación: El rango de los jugadores será {4, 4, 3, 2, 1}.
Hay 5 elementos de array cuyos rangos son menores o iguales a 4.
Por lo tanto, la respuesta es 5.

Enfoque ingenuo: el enfoque más simple es encontrar el elemento máximo actual en la array y compararlo con el elemento máximo anterior. Si son iguales, entonces el rango del elemento anterior y el elemento actual deben ser iguales. De lo contrario, asigne el rango del elemento máximo actual como uno mayor que el número de máximos obtenidos anteriormente. Repita esto hasta que la array dada quede vacía o el rango sea mayor que K , lo que ocurra primero. Después de atravesar, imprima el número total de elementos eliminados. 

Tiempo Complejidad: O(N ² )
Espacio Auxiliar: O(N)

Enfoque eficiente: la idea es utilizar el algoritmo de clasificación . Después de ordenar la array dada en orden no creciente y para cada elemento, si el elemento actual y el anterior no son iguales, entonces el rango del elemento actual debe ser uno mayor que el elemento anterior. Por lo demás, se mantiene igual que el anterior. Siga los pasos a continuación para resolver el problema:

• Ordene el arr[] dado en orden ascendente.
• Inicialice el rango y la posición de la variable con 1 para almacenar el rango y la posición del elemento de array actual, respectivamente.
• Recorra la array ordenada de i = (N – 1) a 0 y realice las siguientes operaciones:
  • Actualice el rango con la posición cuando los elementos de array adyacentes no sean iguales o cuando i sea igual a (N – 1) .
  • Posición de retorno : 1 si el rango se vuelve mayor que K .
  • Incrementa la posición en cada recorrido.
• Imprima N , si todos los elementos de la array tienen rangos que no excedan K .

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find count of array
// elements with rank less than or
// equal to k
int rankLessThanK(int* arr, int k, int n)
{
     
    // Initialize rank and position
    int rank = 1;
    int position = 1;
 
    // Sort the given array
    sort(arr, arr + n);
 
    // Traverse array from right to left
    for(int i = n - 1; i >= 0; i--)
    {
         
        // Update rank with position, if
        // adjacent elements are unequal
        if (i == n - 1 || arr[i] != arr[i + 1])
        {
            rank = position;
 
            // Return position - 1, if
            // rank greater than k
            if (rank > k)
                return position - 1;
        }
 
        // Increase position
        position++;
    }
    return n;
}
 
// Driver Code
int main()
{
     
    // Given array
    int arr[5] = { 2, 2, 3, 4, 5 };
 
    int N = 5;
 
    // Given K
    int K = 4;
 
    // Function Call
    cout << rankLessThanK(arr, K, N);
     
    return 0;
}
 
// This code is contributed by hemanth gadarla

// Java program for the above approach
 
import java.util.*;
import java.lang.*;
class GFG {
 
    // Function to find count of array
    // elements with rank less than or
    // equal to k
    static int rankLessThanK(int[] arr,
                             int k, int n)
    {
        // Initialize rank and position
        int rank = 1;
        int position = 1;
 
        // Sort the given array
        Arrays.sort(arr);
 
        // Traverse array from right to left
        for (int i = n - 1; i >= 0; i--) {
 
            // Update rank with position, if
            // adjacent elements are unequal
            if (i == n - 1
                || arr[i] != arr[i + 1]) {
 
                rank = position;
 
                // Return position - 1, if
                // rank greater than k
                if (rank > k)
                    return position - 1;
            }
 
            // Increase position
            position++;
        }
 
        return n;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        // Given array
        int arr[] = { 2, 2, 3, 4, 5 };
 
        int N = arr.length;
 
        // Given K
        int K = 4;
 
        // Function Call
        System.out.println(
            rankLessThanK(arr, K, N));
    }
}

# Python3 program for the
# above approach
 
# Function to find count of
# array elements with rank
# less than or equal to k
def rankLessThanK(arr, k, n):
   
    # Initialize rank and
    # position
    rank = 1;
    position = 1;
 
    # Sort the given array
    arr = sorted(arr)
 
    # Traverse array from
    # right to left
    for i in range(n - 1,
                   -1, -1):
 
        # Update rank with position,
        # if adjacent elements are
        # unequal
        if (i == n - 1 or
            arr[i] != arr[i + 1]):
            rank = position;
 
            # Return position - 1, if
            # rank greater than k
            if (rank > k):
                return position - 1;
 
        # Increase position
        position += 1;
 
    return n;
 
# Driver Code
if __name__ == '__main__':
   
    # Given array
    arr = [2, 2, 3, 4, 5];
 
    N = len(arr);
 
    # Given K
    K = 4;
 
    # Function Call
    print(rankLessThanK(arr, K, N));
 
# This code is contributed by gauravrajput1

// C# program for the above approach
using System;
  
class GFG{
      
// Function to find count of array
// elements with rank less than or
// equal to k
static int rankLessThanK(int[] arr,
                         int k, int n)
{
     
    // Initialize rank and position
    int rank = 1;
    int position = 1;
 
    // Sort the given array
    Array.Sort(arr);
     
    // Traverse array from right to left
    for(int i = n - 1; i >= 0; i--)
    {
         
        // Update rank with position, if
        // adjacent elements are unequal
        if (i == n - 1 || arr[i] != arr[i + 1])
        {
            rank = position;
 
            // Return position - 1, if
            // rank greater than k
            if (rank > k)
                return position - 1;
        }
 
        // Increase position
        position++;
    }
    return n;
}      
  
// Driver Code
public static void Main()
{
     
    // Given array
    int[] arr = { 2, 2, 3, 4, 5 };
  
    int N = arr.Length;
  
    // Given K
    int K = 4;
  
    // Function Call
    Console.WriteLine(rankLessThanK(
        arr, K, N));
}
}
 
// This code is contributed by sanjoy_62

<script>
 
// Javascript program for the above approach
 
// Function to find count of array
// elements with rank less than or
// equal to k
function rankLessThanK(arr, k, n)
{
     
    // Initialize rank and position
    let rank = 1;
    let position = 1;
 
    // Sort the given array
    arr.sort();
 
    // Traverse array from right to left
    for(let i = n - 1; i >= 0; i--)
    {
         
        // Update rank with position, if
        // adjacent elements are unequal
        if (i == n - 1 || arr[i] != arr[i + 1])
        {
            rank = position;
             
            // Return position - 1, if
            // rank greater than k
            if (rank > k)
                return position - 1;
        }
 
        // Increase position
        position++;
    }
    return n;
}
 
// Driver code
 
// Given array
let arr = [ 2, 2, 3, 4, 5 ];
let N = arr.length;
 
// Given K
let K = 4;
 
// Function Call
document.write(rankLessThanK(arr, K, N));
 
// This code is contributed by splevel62   
 
</script>

5

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