Dada una array arr[] de tamaño N que no tiene duplicados y un número entero K , la tarea es encontrar el K -ésimo elemento más pequeño de la array en un espacio adicional constante y la array no se puede modificar.
Ejemplos:
Entrada: arr[] = {7, 10, 4, 3, 20, 15}, K = 3
Salida: 7 La
array dada ordenada es {3, 4, 7, 10, 15, 20}
donde 7 es el tercero más pequeño elemento.
Entrada: arr[] = {12, 3, 5, 7, 19}, K = 2
Salida: 5
Enfoque: Primero encontramos el elemento mínimo y máximo de la array. Luego establecemos low = min , high = max y mid = (low + high) / 2 .
Ahora, realice una búsqueda binaria modificada, y para cada mid contamos el número de elementos menores que mid e iguales a mid . Si contarMenos < k y contarMenos + contarIgual ≥ k entonces mid es nuestra respuesta, de lo contrario tenemos que modificar nuestro mínimo y máximo.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the kth smallest
// element from the array
int kthSmallest(int* arr, int k, int n)
{
// Minimum and maximum element from the array
int low = *min_element(arr, arr + n);
int high = *max_element(arr, arr + n);
// Modified binary search
while (low <= high) {
int mid = low + (high - low) / 2;
// To store the count of elements from the array
// which are less than mid and
// the elements which are equal to mid
int countless = 0, countequal = 0;
for (int i = 0; i < n; ++i) {
if (arr[i] < mid)
++countless;
else if (arr[i] == mid)
++countequal;
}
// If mid is the kth smallest
if (countless < k
&& (countless + countequal) >= k) {
return mid;
}
// If the required element is less than mid
else if (countless >= k) {
high = mid - 1;
}
// If the required element is greater than mid
else if (countless < k
&& countless + countequal < k) {
low = mid + 1;
}
}
}
// Driver code
int main()
{
int arr[] = { 7, 10, 4, 3, 20, 15 };
int n = sizeof(arr) / sizeof(int);
int k = 3;
cout << kthSmallest(arr, k, n);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
// Function to return the kth smallest
// element from the array
static int kthSmallest(int[] arr, int k, int n)
{
// Minimum and maximum element from the array
int low = Arrays.stream(arr).min().getAsInt();
int high = Arrays.stream(arr).max().getAsInt();
// Modified binary search
while (low <= high)
{
int mid = low + (high - low) / 2;
// To store the count of elements from the array
// which are less than mid and
// the elements which are equal to mid
int countless = 0, countequal = 0;
for (int i = 0; i < n; ++i)
{
if (arr[i] < mid)
++countless;
else if (arr[i] == mid)
++countequal;
}
// If mid is the kth smallest
if (countless < k
&& (countless + countequal) >= k)
{
return mid;
}
// If the required element is less than mid
else if (countless >= k)
{
high = mid - 1;
}
// If the required element is greater than mid
else if (countless < k
&& countless + countequal < k)
{
low = mid + 1;
}
}
return Integer.MIN_VALUE;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 7, 10, 4, 3, 20, 15 };
int n = arr.length;
int k = 3;
System.out.println(kthSmallest(arr, k, n));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 implementation of the approach # Function to return the kth smallest # element from the array def kthSmallest(arr, k, n) : # Minimum and maximum element from the array low = min(arr); high = max(arr); # Modified binary search while (low <= high) : mid = low + (high - low) // 2; # To store the count of elements from the array # which are less than mid and # the elements which are equal to mid countless = 0; countequal = 0; for i in range(n) : if (arr[i] < mid) : countless += 1; elif (arr[i] == mid) : countequal += 1; # If mid is the kth smallest if (countless < k and (countless + countequal) >= k) : return mid; # If the required element is less than mid elif (countless >= k) : high = mid - 1; # If the required element is greater than mid elif (countless < k and countless + countequal < k) : low = mid + 1; # Driver code if __name__ == "__main__" : arr = [ 7, 10, 4, 3, 20, 15 ]; n = len(arr); k = 3; print(kthSmallest(arr, k, n)); # This code is contributed by AnkitRai01
C#
// C# implementation of the approach
using System;
using System.Linq;
class GFG
{
// Function to return the kth smallest
// element from the array
static int kthSmallest(int[] arr, int k, int n)
{
// Minimum and maximum element from the array
int low = arr.Min();
int high = arr.Max();
// Modified binary search
while (low <= high)
{
int mid = low + (high - low) / 2;
// To store the count of elements from the array
// which are less than mid and
// the elements which are equal to mid
int countless = 0, countequal = 0;
for (int i = 0; i < n; ++i)
{
if (arr[i] < mid)
++countless;
else if (arr[i] == mid)
++countequal;
}
// If mid is the kth smallest
if (countless < k
&& (countless + countequal) >= k)
{
return mid;
}
// If the required element is less than mid
else if (countless >= k)
{
high = mid - 1;
}
// If the required element is greater than mid
else if (countless < k
&& countless + countequal < k)
{
low = mid + 1;
}
}
return int.MinValue;
}
// Driver code
public static void Main(String[] args)
{
int []arr = { 7, 10, 4, 3, 20, 15 };
int n = arr.Length;
int k = 3;
Console.WriteLine(kthSmallest(arr, k, n));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript implementation of the approach
// Function to return the kth smallest
// element from the array
function kthSmallest(arr, k, n) {
let temp = [...arr];
// Minimum and maximum element from the array
let low = temp.sort((a, b) => a - b)[0];
let high = temp[temp.length - 1];
// Modified binary search
while (low <= high) {
let mid = low + Math.floor((high - low) / 2);
// To store the count of elements from the array
// which are less than mid and
// the elements which are equal to mid
let countless = 0, countequal = 0;
for (let i = 0; i < n; ++i) {
if (arr[i] < mid)
++countless;
else if (arr[i] == mid)
++countequal;
}
// If mid is the kth smallest
if (countless < k
&& (countless + countequal) >= k) {
return mid;
}
// If the required element is less than mid
else if (countless >= k) {
high = mid - 1;
}
// If the required element is greater than mid
else if (countless < k
&& countless + countequal < k) {
low = mid + 1;
}
}
}
// Driver code
let arr = [7, 10, 4, 3, 20, 15];
let n = arr.length;
let k = 3;
document.write(kthSmallest(arr, k, n));
// This code is contributed by gfgking
</script>
Producción:
7
Complejidad de tiempo: O(N log(Max – Min)) donde Max y Min son los elementos máximo y mínimo de la array respectivamente y N es el tamaño de la array.