Encontrar el número K-ésimo más grande en una array dada de números grandes

Dada una array arr[] de strings que representan números grandes y un entero K, la tarea es encontrar el K -ésimo entero más grande en la array dada.

Ejemplos: 

Entrada: arr[] = { “10”, “7”, “3”, “6” }, K = 3
Salida: “6”
Explicación: ordenar la array en forma no decreciente dará { “3”, “ 6”, “7”, “10” }.
Claramente, el tercer entero más grande es 6.

Entrada: arr[] = { “10”, “7”, “6”, “7”, “11” }, K = 2
Salida:  “10”
Explicación: La disposición de la array en forma no decreciente dará { “ 6”, “7”, “7”, “10”, “11” }
Claramente, el segundo entero más grande es 10.

Enfoque ingenuo (incorrecto): por lo general, este tipo de problemas se pueden resolver convirtiendo strings en números enteros y luego encontrando el K-ésimo número más grande. Pero dado que estamos hablando de números grandes, es decir, strings que representan números enteros de hasta 100 de longitud , no es posible convertirlos en números enteros .

Enfoque correcto: este problema se puede resolver utilizando el enfoque codicioso mediante la implementación de un comparador personalizado. 

Siga los pasos a continuación para resolver el problema dado. 

• Utilice la ordenación personalizada para ordenar la array en orden no decreciente.
• En la función de clasificación personalizada habrá dos casos:
  • El tamaño de las dos strings pasadas es igual, luego intercambie solo cuando la string una sea lexicográficamente más pequeña que la otra.
  • El tamaño de dos strings pasadas no es igual, luego intercambie solo cuando el tamaño de una string sea más pequeño que el otro.
• Después de ordenar, imprima el K-ésimo entero más grande.

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

// C++ implementation for above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Custom comparator to sort
// the array of strings
bool comp(string& a, string& b)
{
    // If sizes of string a and b are equal
    // then return true if a is
    // lexicographically smaller than b
    if (a.size() == b.size())
        return a < b;
 
    // Return true if size of a
    // is smaller than b
    return a.size() < b.size();
}
 
// Function that returns
// kth largest integer
string kthLargestInteger(
    string arr[], int n, int k)
{
 
    // Sort string arr in non-decreasing order
    // using custom comparator function
    sort(arr, arr + n, comp);
 
    return arr[n - k];
}
 
// Driver Code
int main()
{
    int N = 4;
    string arr[N] = { "10", "7", "3", "6" };
    int K = 4;
 
    cout << kthLargestInteger(arr, N, K)
         << endl;
 
    return 0;
}

// Java code for the above approach
import java.util.*;
 
class GFG {
    // Custom comparator to sort
    // the array of strings
 
    // Function that returns
    // kth largest integer
    static String kthLargestInteger(String arr[], int n,
                                    int k)
    {
 
        // Sort string arr in non-decreasing order
        // using custom comparator function
        Arrays.sort(arr, new Comparator<String>() {
            @Override public int compare(String a, String b)
            {
                return Integer.valueOf(a).compareTo(
                    Integer.valueOf(b));
            }
        });
 
        return arr[n - k];
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int N = 4;
        String arr[] = { "10", "7", "3", "6" };
        int K = 4;
 
        System.out.println(kthLargestInteger(arr, N, K));
    }
}
 
// This code is contributed by Potta Lokesh

# Python 3 implementation for above approach
 
# Function that returns
# kth largest integer
def kthLargestInteger(
        arr, n, k):
 
    # Sort string arr in non-decreasing order
    # using custom comparator function
    arr = [int(i) for i in arr]
    arr.sort()
 
    return arr[n - k]
 
# Driver Code
if __name__ == "__main__":
 
    N = 4
    arr = ["10", "7", "3", "6"]
    K = 4
 
    print(kthLargestInteger(arr, N, K))
 
    # This code is contributed by ukasp.

// C# code for the above approach
using System;
 
public class GFG
{
 
  // Custom comparator to sort
  // the array of strings
 
  // Function that returns
  // kth largest integer
  static String kthLargestint(String []arr, int n,
                              int k)
  {
 
    // Sort string arr in non-decreasing order
    // using custom comparator function
    Array.Sort(arr,CompareStrings);
 
    return arr[n - k];
  }
  static int CompareStrings(string a, string b)
  {
    return Int32.Parse(a).CompareTo(
      Int32.Parse(b));
  }
   
  // Driver Code
  public static void Main(String[] args)
  {
    int N = 4;
    String []arr = { "10", "7", "3", "6" };
    int K = 4;
 
    Console.WriteLine(kthLargestint(arr, N, K));
  }
}
 
// This code is contributed by 29AjayKumar

<script>
 
// Javsacript implementation for above approach
 
// Custom comparator to sort
// the array of strings
function comp(a, b)
{
 
  // If sizes of string a and b are equal
  // then return true if a is
  // lexicographically smaller than b
  if (a.length == b.length)
    return a - b;
 
  // Return true if size of a
  // is smaller than b
  return (a.length - b.length);
}
 
// Function that returns
// kth largest integer
function kthLargestInteger(arr, n, k) {
 
  // Sort string arr in non-decreasing order
  // using custom comparator function
  arr.sort(comp);
  console.log(arr)
 
  return arr[n - k];
}
 
// Driver Code
 
let N = 4;
let arr = ["10", "7", "3", "6"];
let K = 4;
 
document.write(kthLargestInteger(arr, N, K))
 
// This code is contributed by saurbh_jaiswal.
</script>

3

Complejidad de tiempo: O (N * log N), donde N es el tamaño de la array. 

Espacio Auxiliar: O(1)