K-ésimo elemento más pequeño o más grande en una array no clasificada | conjunto 4

Dada una array arr[] y un número K , donde K es más pequeño que el tamaño de la array, necesitamos encontrar el K-ésimo elemento más pequeño en la array dada. Se da que los elementos de la array se pueden repetir (no limitados a distintos).

Ejemplos: 

Entrada: arr[] = {7, 10, 4, 3, 20, 15}, K = 3 
Salida: 7

Entrada: arr[] = {7, 1, 5, 4, 20, 15, 8}, K = 5 
Salida: 8 

Hemos discutido este artículo con otros enfoques también: 

• K’th elemento más pequeño/más grande en array no ordenada | Serie 1
• K’th elemento más pequeño/más grande en array no ordenada | Conjunto 2 (Tiempo lineal esperado)
• K’th elemento más pequeño/más grande en array no ordenada | Conjunto 3 (Tiempo lineal en el peor de los casos)

Planteamiento: La idea es utilizar el concepto de Ordenación Contable . A continuación se muestran los pasos: 

1. Encuentre el elemento máximo (digamos maxE ) en la array y cree una array (digamos freq[] ) de longitud maxE + 1 e inicialícela a cero.
2. Recorra todos los elementos en la array dada y almacene la frecuencia del elemento en freq[] .
3. Iterar sobre la array freq[] hasta llegar al elemento K-ésimo .
4. Imprime el K-ésimo elemento alcanzado en el paso anterior.

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

// C++ program for the above approach
#include <iostream>
using namespace std;
 
// Function to find the Kth smallest
// element in Unsorted Array
int findKthSmallest(int arr[], int n, int k)
{
 
    // Initialize the max Element as 0
    int max = 0;
 
    // Iterate arr[] and find the maximum
    // element in it
    for (int i = 0; i < n; i++)
    {
        if (arr[i] > max)
            max = arr[i];
    }
 
    // Frequency array to store
    // the frequencies
    int counter[max + 1] = { 0 };
 
    // Counter variable
    int smallest = 0;
 
    // Counting the frequencies
    for (int i = 0; i < n; i++)
    {
        counter[arr[i]]++;
    }
 
    // Iterate through the freq[]
    for (int num = 1; num <= max; num++)
    {
        // Check if num is present
        // in the array
        if (counter[num] > 0) {
 
            // Increment the counter
            // with the frequency
            // of num
            smallest += counter[num];
        }
 
        // Checking if we have reached
        // the Kth smallest element
        if (smallest >= k)
        {
            // Return the Kth
            // smallest element
            return num;
        }
    }
}
 
// Driver Code
int main()
{
    // Given array
    int arr[] = { 7, 1, 4, 4, 20, 15, 8 };
 
    int N = sizeof(arr) / sizeof(arr[0]);
 
    int K = 5;
 
    // Function Call
    cout << findKthSmallest(arr, N, K);
 
    return 0;
}

// Java program for the above approach
import java.io.*;
 
class GFG {
 
    // Function to find the Kth smallest
    // element in Unsorted Array
    static int findKthSmallest(int[] arr, int n, int k)
    {
 
        // Initialize the max Element as 0
        int max = 0;
 
        // Iterate arr[] and find the maximum
        // element in it
        for (int i = 0; i < n; i++)
        {
            if (arr[i] > max)
                max = arr[i];
        }
 
        // Frequency array to store
        // the frequencies
        int[] counter = new int[max + 1];
 
        // Counter variable
        int smallest = 0;
 
        // Counting the frequencies
        for (int i = 0; i < n; i++)
        {
            counter[arr[i]]++;
        }
 
        // Iterate through the freq[]
        for (int num = 1; num <= max; num++)
        {
            // Check if num is present
            // in the array
            if (counter[num] > 0)
            {
                // Increment the counter
                // with the frequency
                // of num
                smallest += counter[num];
            }
 
            // Checking if we have reached
            // the Kth smallest element
            if (smallest >= k)
            {
                // Return the Kth
                // smallest element
                return num;
            }
        }
        return -1;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        // Given array
        int[] arr = { 7, 1, 4, 4, 20, 15, 8 };
 
        int N = arr.length;
 
        int K = 5;
 
        // Function call
        System.out.print(findKthSmallest(arr, N, K));
    }
}

# Python3 program for the
# above approach
 
# Function to find the Kth
# smallest element in Unsorted
# Array
def findKthSmallest(arr, n, k):
 
    # Initialize the max
    # Element as 0
    max = 0
 
    # Iterate arr[] and find
    # the maximum element in it
    for i in range(n):
        if (arr[i] > max):
            max = arr[i]
 
    # Frequency array to
    # store the frequencies
    counter = [0] * (max + 1)
 
    # Counter variable
    smallest = 0
 
    # Counting the frequencies
    for i in range(n):
        counter[arr[i]] += 1
 
    # Iterate through the freq[]
    for num in range(1, max + 1):
 
        # Check if num is present
        # in the array
        if (counter[num] > 0):
 
            # Increment the counter
            # with the frequency
            # of num
            smallest += counter[num]
 
        # Checking if we have reached
        # the Kth smallest element
        if (smallest >= k):
 
            # Return the Kth
            # smallest element
            return num
 
# Driver Code
if __name__ == "__main__":
 
    # Given array
    arr = [7, 1, 4, 4,
           20, 15, 8]
 
    N = len(arr)
    K = 5
 
    # Function Call
    print(findKthSmallest(arr, N, K))
 
# This code is contributed by Chitranayal

// C# program for the
// above approach
using System;
using System.Collections.Generic;
class GFG{
 
// Function to find the Kth smallest
// element in Unsorted Array
static int findKthSmallest(int[] arr,
                           int n, int k)
{
  // Initialize the max
  // Element as 0
  int max = 0;
 
  // Iterate []arr and find
  // the maximum element in it
  for (int i = 0; i < n; i++)
  {
    if (arr[i] > max)
      max = arr[i];
  }
 
  // Frequency array to store
  // the frequencies
  int[] counter = new int[max + 1];
 
  // Counter variable
  int smallest = 0;
 
  // Counting the frequencies
  for (int i = 0; i < n; i++)
  {
    counter[arr[i]]++;
  }
 
  // Iterate through the []freq
  for (int num = 1;
           num <= max; num++)
  {
    // Check if num is present
    // in the array
    if (counter[num] > 0)
    {
      // Increment the counter
      // with the frequency
      // of num
      smallest += counter[num];
    }
 
    // Checking if we have reached
    // the Kth smallest element
    if (smallest >= k)
    {
      // Return the Kth
      // smallest element
      return num;
    }
  }
  return -1;
}
 
// Driver code
public static void Main(String[] args)
{
  // Given array
  int[] arr = {7, 1, 4, 4,
               20, 15, 8};
  int N = arr.Length;
  int K = 5;
 
  // Function call
  Console.Write(findKthSmallest(arr,
                                N, K));
}
}
 
// This code is contributed by shikhasingrajput

<script>
 
// JavaScript program for the above approach
 
    // Function to find the Kth smallest
    // element in Unsorted Array
    function findKthSmallest(arr, n, k)
    {
 
        // Initialize the max Element as 0
        let max = 0;
 
        // Iterate arr[] and find the maximum
        // element in it
        for (let i = 0; i < n; i++)
        {
            if (arr[i] > max)
                max = arr[i];
        }
 
        // Frequency array to store
        // the frequencies
        let counter = Array.from({length: max + 1}, (_, i) => 0);
 
        // Counter variable
        let smallest = 0;
 
        // Counting the frequencies
        for (let i = 0; i < n; i++)
        {
            counter[arr[i]]++;
        }
 
        // Iterate through the freq[]
        for (let num = 1; num <= max; num++)
        {
            // Check if num is present
            // in the array
            if (counter[num] > 0)
            {
                // Increment the counter
                // with the frequency
                // of num
                smallest += counter[num];
            }
 
            // Checking if we have reached
            // the Kth smallest element
            if (smallest >= k)
            {
                // Return the Kth
                // smallest element
                return num;
            }
        }
        return -1;
    }
  
// Driver Code
 
    // Given array
        let arr = [ 7, 1, 4, 4, 20, 15, 8 ];
 
        let N = arr.length;
 
        let K = 5;
 
        // Function call
        document.write(findKthSmallest(arr, N, K));
  
 // This code is contributed by sanjoy_62.
</script>

8

Complejidad de tiempo: O(N+MaxElement) donde N es el número de elementos en la array dada y MaxElement es el número máximo en la array. Complejidad pseudo-lineal-temporal. 
Espacio Auxiliar: O(M) donde M es el elemento máximo en el arreglo dado.