Número de jugadores cuyo rango es igual o menor que un rango de corte dado

Dada una array arr[] que consta de N enteros y un entero R , que denota el rango de corte, la tarea es contar el número de elementos de la array con rango como máximo R de modo que los elementos de la array iguales se clasifiquen de la misma manera y los elementos de la array distintos sean clasificados en función de sus posiciones en la array arr[] .

Ejemplos:

Entrada: arr[] = {100, 50, 50, 25}, R = 3
Salida: 3
Explicación:
Los jugadores están clasificados como: {1, 2, 2, 4}. Los jugadores que han clasificado como máximo R(= 3) son {1, 2, 2}. Por lo tanto, la cuenta total es 3.

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

Enfoque: El problema dado se puede resolver utilizando el concepto de clasificación . Siga el siguiente paso para resolver este problema:

• Ordene la array dada arr[] en orden decreciente .
• Inicialice dos variables, diga rango como 1 para almacenar el rango de los elementos de la array y diga contar como 0 para almacenar el resultado requerido.
• Recorra la array dada arr[] , usando la variable i , y realice los siguientes pasos:
  • Si arr[i] es igual al elemento anterior, asigne el mismo rango que el rango anterior al elemento actual.
  • De lo contrario, asigne el valor de (recuento + 1) ^th rango al elemento actual.
  • Si el rango es mayor que R , se rompe. De lo contrario, incremente el conteo en 1 .
• Después de completar los pasos anteriores, imprima el valor de count como respuesta.

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

// C++  program for above approach
#include <algorithm>
#include <iostream>
using namespace std;
 
// Function to find the count of array
// elements having rank at most R
int countElements(int R, int N, int arr[])
{
 
  // Sort the array arr[] in the
  // decreasing order
  sort(arr, arr + N, greater<int>());
 
  // Stores the rank and required
  // count of array elements
  int rank = 1, count = 0;
 
  // store the previou element
  int prevScore = arr[0], score;
 
  // Traverse the array
  for (int i = 0; i < N; i++) {
    score = arr[i];
 
    // If score is less than the
    // prevScore
    if (score < prevScore) {
      rank = count + 1;
    }
 
    // If the rank is greater than R
    if (rank > R) {
      break;
    }
 
    // Increment count by 1
    count++;
 
    // update prevscore
    prevScore = score;
  }
 
  // return count
  return count;
}
 
// Driver code
int main()
{
  int arr[] = { 100, 50, 50, 25 };
  int R = 2;
  int N = sizeof(arr) / sizeof(arr[0]);
  cout << countElements(R, N, arr);
  return 0;
}
 
// This code is contributed by Parth Manchanda

// Java program for the above approach
import java.util.*;
 
class GFG
{
  static void reverse(int a[])
  {
    int n = a.length;
    int[] b = new int[n];
    int j = n;
    for (int i = 0; i < n; i++) {
      b[j - 1] = a[i];
      j = j - 1;
    }
  }
 
  // Function to find the count of array
  // elements having rank at most R
  static int countElements(int R, int N, int[] arr)
  {
 
    // Sort the array arr[] in the
    // decreasing order
    Arrays.sort(arr);
    reverse(arr);
 
    // Stores the rank and required
    // count of array elements
    int rank = 1;
    int count = -1;
 
    // Stores the previous element
    int prevScore = arr[0];
 
    // Traverse the array
    for(int score : arr)
    {
 
      // If score is less than the
      // prevScore
      if (score < prevScore)
        rank = count + 1;
 
      // If the rank is greater than R
      if (rank > R)
        break;
 
      // Increment count by 1
      count = count + 1;
 
      // Update prevScore
      prevScore = score;
    }
 
    // Return the result
    return count;
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    int[] arr = { 100, 50, 50, 25 };
    int R = 2;
    int N = arr.length;
 
    // Function Call
    System.out.println(countElements(R, N, arr));
  }
}
 
// This code is contributed by sanjoy_62.

# Python program for the above approach
 
# Function to find the count of array
# elements having rank at most R
def countElements(R, N, arr):
 
    # Sort the array arr[] in the
    # decreasing order
    arr.sort(reverse = True)
 
    # Stores the rank and required
    # count of array elements
    rank = 1
    count = 0
 
    # Stores the previous element
    prevScore = arr[0]
 
    # Traverse the array
    for score in arr:
 
        # If score is less than the
        # prevScore
        if score < prevScore:
            rank = count + 1
 
        # If the rank is greater than R
        if rank > R:
            break
             
        # Increment count by 1
        count += 1
 
        # Update prevScore
        prevScore = score
 
    # Return the result
    return count
 
 
# Driver Code
arr = [100, 50, 50, 25]
R = 2
N = len(arr)
 
# Function Call
print(countElements(R, N, arr))

// C# program for the above approach
using System;
 
class GFG{
     
// Function to find the count of array
// elements having rank at most R
static int countElements(int R, int N, int[] arr)
{
     
    // Sort the array arr[] in the
    // decreasing order
    Array.Sort(arr);
    Array.Reverse(arr);
 
    // Stores the rank and required
    // count of array elements
    int rank = 1;
    int count = 0;
 
    // Stores the previous element
    int prevScore = arr[0];
 
    // Traverse the array
    foreach(int score in arr)
    {
         
        // If score is less than the
        // prevScore
        if (score < prevScore)
            rank = count + 1;
 
        // If the rank is greater than R
        if (rank > R)
            break;
 
        // Increment count by 1
        count = count + 1;
 
        // Update prevScore
        prevScore = score;
    }
     
    // Return the result
    return count;
}
 
 
// Driver code
static public void Main()
{
    int[] arr = { 100, 50, 50, 25 };
    int R = 2;
    int N = arr.Length;
 
    // Function Call
    Console.WriteLine(countElements(R, N, arr));
}
}
 
// This code is contributed by target_2.

<script>
 
// JavaScript program for the above approach
 
// Function to find the count of array
// elements having rank at most R
function countElements(R, N, arr)
{
     
    // Sort the array arr[] in the
    // decreasing order
    arr.sort(function(a, b){ return b - a; });
 
    // Stores the rank and required
    // count of array elements
    let rank = 1;
    let count = 0;
 
    // Stores the previous element
    let prevScore = arr[0];
 
    // Traverse the array
    for(let score of arr)
    {
         
        // If score is less than the
        // prevScore
        if (score < prevScore)
            rank = count + 1;
 
        // If the rank is greater than R
        if (rank > R)
            break;
 
        // Increment count by 1
        count = count + 1;
 
        // Update prevScore
        prevScore = score;
    }
     
    // Return the result
    return count;
}
 
// Driver Code
let arr = [ 100, 50, 50, 25 ];
let R = 2;
let N = arr.length;
 
// Function Call
document.write(countElements(R, N, arr));
 
// This code is contributed by lokeshpotta20
 
</script>

3

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