Encuentre el k-ésimo elemento más pequeño o más grande en una array no ordenada, donde k<=tamaño de la array. Se da que los elementos de la array están en un rango pequeño.
Ejemplos:
Input : arr[] = {3, 2, 9, 5, 7, 11, 13} k = 5 Output: 9 Input : arr[] = {16, 8, 9, 21, 43} k = 3 Output: 16 Input : arr[] = {50, 50, 40} k = 2 Output: 50
Como los elementos de array dados están en un rango pequeño, podemos dirigir la tabla de índice para que haga algo similar a ordenar por conteo . Almacenamos recuentos de elementos, luego recorremos la array de recuento e imprimimos el k-ésimo elemento.
A continuación se muestra la implementación del algoritmo anterior.
C++
// C++ program of kth smallest/largest in // a small range unsorted array #include <bits/stdc++.h> using namespace std; #define maxs 1000001 int kthSmallestLargest(int* arr, int n, int k) { int max_val = *max_element(arr, arr+n); int hash[max_val+1] = { 0 }; // Storing counts of elements for (int i = 0; i < n; i++) hash[arr[i]]++; // Traverse hash array build above until // we reach k-th smallest element. int count = 0; for (int i=0; i <= max_val; i++) { while (hash[i] > 0) { count++; if (count == k) return i; hash[i]--; } } return -1; } int main() { int arr[] = { 11, 6, 2, 9, 4, 3, 16 }; int n = sizeof(arr) / sizeof(arr[0]), k = 3; cout << "kth smallest number is: " << kthSmallestLargest(arr, n, k) << endl; return 0; }
Java
// Java program of kth smallest/largest in // a small range unsorted array import java.util.Arrays; class GFG { static int maxs = 1000001; static int kthSmallestLargest(int[] arr, int n, int k) { int max_val = Arrays.stream(arr).max().getAsInt(); int hash[] = new int[max_val + 1]; // Storing counts of elements for (int i = 0; i < n; i++) { hash[arr[i]]++; } // Traverse hash array build above until // we reach k-th smallest element. int count = 0; for (int i = 0; i <= max_val; i++) { while (hash[i] > 0) { count++; if (count == k) { return i; } hash[i]--; } } return -1; } // Driver code public static void main(String[] args) { int arr[] = {11, 6, 2, 9, 4, 3, 16}; int n = arr.length, k = 3; System.out.println("kth smallest number is: " + kthSmallestLargest(arr, n, k)); } } // This code has been contributed by 29AjayKumar
Python3
# Python 3 program of kth smallest/largest # in a small range unsorted array def kthSmallestLargest(arr, n, k): max_val = arr[0] for i in range(len(arr)): if (arr[i] > max_val): max_val = arr[i] hash = [0 for i in range(max_val + 1)] # Storing counts of elements for i in range(n): hash[arr[i]] += 1 # Traverse hash array build above until # we reach k-th smallest element. count = 0 for i in range(max_val + 1): while (hash[i] > 0): count += 1 if (count == k): return i hash[i] -= 1 return -1 # Driver Code if __name__ == '__main__': arr = [11, 6, 2, 9, 4, 3, 16] n = len(arr) k = 3 print("kth smallest number is:", kthSmallestLargest(arr, n, k)) # This code is contributed by # Surendra_Gangwar
C#
// C# program of kth smallest/largest in // a small range unsorted array using System; using System.Linq; class GFG { static int maxs = 1000001; static int kthSmallestLargest(int[] arr, int n, int k) { int max_val = arr.Max(); int []hash = new int[max_val + 1]; // Storing counts of elements for (int i = 0; i < n; i++) { hash[arr[i]]++; } // Traverse hash array build above until // we reach k-th smallest element. int count = 0; for (int i = 0; i <= max_val; i++) { while (hash[i] > 0) { count++; if (count == k) { return i; } hash[i]--; } } return -1; } // Driver code public static void Main() { int []arr = {11, 6, 2, 9, 4, 3, 16}; int n = arr.Length, k = 3; Console.WriteLine("kth smallest number is: " + kthSmallestLargest(arr, n, k)); } } /* This code contributed by PrinciRaj1992 */
PHP
<?php // PHP program of kth smallest/largest in // a small range unsorted array $maxs = 1000001; function kthSmallestLargest(&$arr, $n, $k) { global $maxs; $max_val = max($arr); $hash = array_fill(0,$max_val+1, NULL); // Storing counts of elements for ($i = 0; $i < $n; $i++) $hash[$arr[$i]]++; // Traverse hash array build above until // we reach k-th smallest element. $count = 0; for ($i=0; $i <= $max_val; $i++) { while ($hash[$i] > 0) { $count++; if ($count == $k) return $i; $hash[$i]--; } } return -1; } $arr = array ( 11, 6, 2, 9, 4, 3, 16 ); $n = sizeof($arr) / sizeof($arr[0]); $k = 3; echo "kth smallest number is: " . kthSmallestLargest($arr, $n, $k)."\n"; return 0; ?>
Javascript
<script> // Javascript program of kth smallest/largest in // a small range unsorted array let maxs = 1000001; function kthSmallestLargest(arr,n,k) { let max_val = Math.max(...arr); let hash = new Array(max_val + 1); for(let i=0;i<hash.length;i++) { hash[i]=0; } // Storing counts of elements for (let i = 0; i < n; i++) { hash[arr[i]]++; } // Traverse hash array build above until // we reach k-th smallest element. let count = 0; for (let i = 0; i <= max_val; i++) { while (hash[i] > 0) { count++; if (count == k) { return i; } hash[i]--; } } return -1; } // Driver code let arr=[11, 6, 2, 9, 4, 3, 16]; let n = arr.length, k = 3; document.write("kth smallest number is: " + kthSmallestLargest(arr, n, k)); // This code is contributed by avanitrachhadiya2155 </script>
Producción:
kth smallest number is: 4
Complejidad de tiempo: O(n + max_val)
Publicación traducida automáticamente
Artículo escrito por Dhirendra121 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA