Escriba un programa eficiente para imprimir los k elementos más grandes en una array. Los elementos de una array pueden estar en cualquier orden.
Por ejemplo: si la array dada es [1, 23, 12, 9, 30, 2, 50] y se le piden los 3 elementos más grandes, es decir, k = 3, entonces su programa debe imprimir 50, 30 y 23.
Método 1 (Usar Bubble k veces)
Gracias a Shailendra por sugerir este enfoque.
1) Modifique Bubble Sort para ejecutar el ciclo externo como máximo k veces.
2) Imprime los últimos k elementos del arreglo obtenido en el paso 1.
Complejidad Temporal: O(n*k)
Al igual que Bubble sort, otros algoritmos de clasificación como Selection Sort también se pueden modificar para obtener los k elementos más grandes.
Método 2 (Usar array temporal)
K elementos más grandes de arr[0..n-1]
1) Almacene los primeros k elementos en una array temporal temp[0..k-1].
2) Encuentre el elemento más pequeño en temp[], deje que el elemento más pequeño sea min .
3-a) Para cada elemento x en arr[k] a arr[n-1]. O(nk)
Si x es mayor que min, elimine min de temp[] e inserte x .
3-b) Luego, determine el nuevo mínimo de temp[]. O(k)
4) Imprime los k elementos finales de temp[]
Complejidad temporal: O((nk)*k). Si queremos ordenar la salida, entonces O((nk)*k + k*log(k))
Gracias a nesamani1822 por sugerir este método.
Método 3 (Usar clasificación)
1) Ordenar los elementos en orden descendente en O(n*log(n))
2) Imprimir los primeros k números de la array ordenada O(k).
A continuación se presenta la implementación de lo anterior.
C++
// C++ code for k largest elements in an array
#include <bits/stdc++.h>
using namespace std;
void kLargest(int arr[], int n, int k)
{
// Sort the given array arr in reverse order.
sort(arr, arr + n, greater<int>());
// Print the first kth largest elements
for (int i = 0; i < k; i++)
cout << arr[i] << " ";
}
// driver program
int main()
{
int arr[] = { 1, 23, 12, 9, 30, 2, 50 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 3;
kLargest(arr, n, k);
}
// This code is contributed by Aditya Kumar (adityakumar129)
C
// C code for k largest elements in an array
#include <stdio.h>
#include <stdlib.h>
// Compare function for qsort
int cmpfunc(const void* a, const void* b)
{
return (*(int*)b - *(int*)a);
}
void kLargest(int arr[], int n, int k)
{
// Sort the given array arr in reverse order.
qsort(arr, n, sizeof(int), cmpfunc);
// Print the first kth largest elements
for (int i = 0; i < k; i++)
printf("%d ", arr[i]);
}
// driver program
int main()
{
int arr[] = { 1, 23, 12, 9, 30, 2, 50 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 3;
kLargest(arr, n, k);
}
// This code is contributed by Aditya Kumar (adityakumar129)
Java
// Java code for k largest elements in an array
import java.util.Arrays;
import java.util.Collections;
import java.util.ArrayList;
class GFG {
public static void kLargest(Integer[] arr, int k)
{
// Sort the given array arr in reverse order
// This method doesn't work with primitive data
// types. So, instead of int, Integer type
// array will be used
Arrays.sort(arr, Collections.reverseOrder());
// Print the first kth largest elements
for (int i = 0; i < k; i++)
System.out.print(arr[i] + " ");
}
//This code is contributed by Niraj Dubey
public static ArrayList<Integer> kLargest(int[] arr, int k)
{
//Convert using stream
Integer[] obj_array = Arrays.stream( arr ).boxed().toArray( Integer[] :: new);
Arrays.sort(obj_array, Collections.reverseOrder());
ArrayList<Integer> list = new ArrayList<>(k);
for (int i = 0; i < k; i++)
list.add(obj_array[i]);
return list;
}
public static void main(String[] args)
{
Integer arr[] = new Integer[] { 1, 23, 12, 9,
30, 2, 50 };
int k = 3;
kLargest(arr, k);
//This code is contributed by Niraj Dubey
//What if primitive datatype array is passed and wanted to return in ArrayList<Integer>
int[] prim_array = { 1, 23, 12, 9, 30, 2, 50 };
System.out.print(kLargest(prim_array, k));
}
}
// This code is contributed by Kamal Rawal
Python
''' Python3 code for k largest elements in an array''' def kLargest(arr, k): # Sort the given array arr in reverse # order. arr.sort(reverse = True) # Print the first kth largest elements for i in range(k): print (arr[i], end =" ") # Driver program arr = [1, 23, 12, 9, 30, 2, 50] # n = len(arr) k = 3 kLargest(arr, k) # This code is contributed by shreyanshi_arun.
C#
// C# code for k largest elements in an array
using System;
class GFG {
public static void kLargest(int[] arr, int k)
{
// Sort the given array arr in reverse order
// This method doesn't work with primitive data
// types. So, instead of int, Integer type
// array will be used
Array.Sort(arr);
Array.Reverse(arr);
// Print the first kth largest elements
for (int i = 0; i < k; i++)
Console.Write(arr[i] + " ");
}
// Driver code
public static void Main(String[] args)
{
int[] arr = new int[] { 1, 23, 12, 9,
30, 2, 50 };
int k = 3;
kLargest(arr, k);
}
}
// This code contributed by Rajput-Ji
PHP
<?php
// PHP code for k largest
// elements in an array
function kLargest(&$arr, $n, $k)
{
// Sort the given array arr
// in reverse order.
rsort($arr);
// Print the first kth
// largest elements
for ($i = 0; $i < $k; $i++)
echo $arr[$i] . " ";
}
// Driver Code
$arr = array(1, 23, 12, 9,
30, 2, 50);
$n = sizeof($arr);
$k = 3;
kLargest($arr, $n, $k);
// This code is contributed
// by ChitraNayal
?>
Javascript
<script>
// JavaScript code for k largest
// elements in an array
function kLargest(arr, n, k)
{
// Sort the given array arr in reverse
// order.
arr.sort((a, b) => b - a);
// Print the first kth largest elements
for (let i = 0; i < k; i++)
document.write(arr[i] + " ");
}
// driver program
let arr = [ 1, 23, 12, 9, 30, 2, 50 ];
let n = arr.length;
let k = 3;
kLargest(arr, n, k);
// This code is contributed by Manoj.
</script>
Producción
50 30 23
Complejidad temporal: O(n*log(n))
Espacio auxiliar: O(1)
Método 4 (Usar Max Heap)
1) Construir un árbol Max Heap en O(n)
2) Usar Extraer Max k veces para obtener k elementos máximos del Max Heap O(k*log(n))
Complejidad del tiempo: O(n + k*log(n))
Método 5 (Usar estadísticas de orden)
1) Usar un algoritmo de estadística de orden para encontrar el k-ésimo elemento más grande. Consulte la selección de temas en el peor de los casos en tiempo lineal O(n)
2) Utilice el algoritmo de partición QuickSort para particionar alrededor del késimo número más grande O(n).
3) Ordenar los k-1 elementos (elementos mayores que el k-ésimo elemento más grande) O(k*log(k)). Este paso es necesario solo si se requiere la salida ordenada.
Complejidad del tiempo: O(n) si no necesitamos la salida ordenada; de lo contrario, O(n+k*log(k))
Gracias a Shilpi por sugerir los dos primeros enfoques.
Método 6 (Usar Min Heap)
Este método es principalmente una optimización del método 2. En lugar de usar la array temp[], use Min Heap.
1) Cree un Min Heap MH de los primeros k elementos (arr[0] a arr[k-1]) de la array dada. O (k*log(k))
2) Para cada elemento, después del k-ésimo elemento (arr[k] a arr[n-1]), compárelo con la raíz de MH.
……a) Si el elemento es mayor que la raíz, conviértalo en root y llame a heapify para MH
……b) De lo contrario, ignórelo.
// El paso 2 es O((nk)*log(k))
3) Finalmente, MH tiene k elementos más grandes, y la raíz de MH es el k-ésimo elemento más grande.
Complejidad de tiempo: O(k*log(k) + (nk)*log(k)) sin salida ordenada. Si se necesita una salida ordenada, entonces O(k*log(k) + (nk)*log(k) + k*log(k)) por lo que en general es O(k*log(k) + (nk)*log( k))
Todos los métodos anteriores también se pueden usar para encontrar el k-ésimo elemento más grande (o más pequeño).
C++
#include <iostream>
using namespace std;
// Swap function to interchange
// the value of variables x and y
int swap(int& x, int& y)
{
int temp = x;
x = y;
y = temp;
}
// Min Heap Class
// arr holds reference to an integer
// array size indicate the number of
// elements in Min Heap
class MinHeap {
int size;
int* arr;
public:
// Constructor to initialize the size and arr
MinHeap(int size, int input[]);
// Min Heapify function, that assumes that
// 2*i+1 and 2*i+2 are min heap and fix the
// heap property for i.
void heapify(int i);
// Build the min heap, by calling heapify
// for all non-leaf nodes.
void buildHeap();
};
// Constructor to initialize data
// members and creating mean heap
MinHeap::MinHeap(int size, int input[])
{
// Initializing arr and size
this->size = size;
this->arr = input;
// Building the Min Heap
buildHeap();
}
// Min Heapify function, that assumes
// 2*i+1 and 2*i+2 are min heap and
// fix min heap property for i
void MinHeap::heapify(int i)
{
// If Leaf Node, Simply return
if (i >= size / 2)
return;
// variable to store the smallest element
// index out of i, 2*i+1 and 2*i+2
int smallest;
// Index of left node
int left = 2 * i + 1;
// Index of right node
int right = 2 * i + 2;
// Select minimum from left node and
// current node i, and store the minimum
// index in smallest variable
smallest = arr[left] < arr[i] ? left : i;
// If right child exist, compare and
// update the smallest variable
if (right < size)
smallest = arr[right] < arr[smallest]
? right : smallest;
// If Node i violates the min heap
// property, swap current node i with
// smallest to fix the min-heap property
// and recursively call heapify for node smallest.
if (smallest != i) {
swap(arr[i], arr[smallest]);
heapify(smallest);
}
}
// Build Min Heap
void MinHeap::buildHeap()
{
// Calling Heapify for all non leaf nodes
for (int i = size / 2 - 1; i >= 0; i--) {
heapify(i);
}
}
void FirstKelements(int arr[],int size,int k){
// Creating Min Heap for given
// array with only k elements
MinHeap* m = new MinHeap(k, arr);
// Loop For each element in array
// after the kth element
for (int i = k; i < size; i++) {
// if current element is smaller
// than minimum element, do nothing
// and continue to next element
if (arr[0] > arr[i])
continue;
// Otherwise Change minimum element to
// current element, and call heapify to
// restore the heap property
else {
arr[0] = arr[i];
m->heapify(0);
}
}
// Now min heap contains k maximum
// elements, Iterate and print
for (int i = 0; i < k; i++) {
cout << arr[i] << " ";
}
}
// Driver Program
int main()
{
int arr[] = { 11, 3, 2, 1, 15, 5, 4,
45, 88, 96, 50, 45 };
int size = sizeof(arr) / sizeof(arr[0]);
// Size of Min Heap
int k = 3;
FirstKelements(arr,size,k);
return 0;
}
// This code is contributed by Ankur Goel
Java
import java.io.*;
import java.util.*;
class GFG{
public static void FirstKelements(int arr[],
int size,
int k)
{
// Creating Min Heap for given
// array with only k elements
// Create min heap with priority queue
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for(int i = 0; i < k; i++)
{
minHeap.add(arr[i]);
}
// Loop For each element in array
// after the kth element
for(int i = k; i < size; i++)
{
// If current element is smaller
// than minimum ((top element of
// the minHeap) element, do nothing
// and continue to next element
if (minHeap.peek() > arr[i])
continue;
// Otherwise Change minimum element
// (top element of the minHeap) to
// current element by polling out
// the top element of the minHeap
else
{
minHeap.poll();
minHeap.add(arr[i]);
}
}
// Now min heap contains k maximum
// elements, Iterate and print
Iterator iterator = minHeap.iterator();
while (iterator.hasNext())
{
System.out.print(iterator.next() + " ");
}
}
// Driver code
public static void main (String[] args)
{
int arr[] = { 11, 3, 2, 1, 15, 5, 4,
45, 88, 96, 50, 45 };
int size = arr.length;
// Size of Min Heap
int k = 3;
FirstKelements(arr, size, k);
}
}
// This code is contributed by Vansh Sethi
Python3
#importing heapq module #to implement heap import heapq as hq def FirstKelements(arr, size, k): # Creating Min Heap for given # array with only k elements # Create min heap using heapq module minHeap = [] for i in range(k): minHeap.append(arr[i]) hq.heapify(minHeap) # Loop For each element in array # after the kth element for i in range(k, size): # If current element is smaller # than minimum ((top element of # the minHeap) element, do nothing # and continue to next element if minHeap[0] > arr[i]: continue # Otherwise Change minimum element # (top element of the minHeap) to # current element by polling out # the top element of the minHeap else: #deleting top element of the min heap minHeap[0] = minHeap[-1] minHeap.pop() minHeap.append(arr[i]) #maintaining heap again using # O(n) time operation.... hq.heapify(minHeap) # Now min heap contains k maximum # elements, Iterate and print for i in minHeap: print(i, end=" ") # Driver code arr = [11, 3, 2, 1, 15, 5, 4, 45, 88, 96, 50, 45] size = len(arr) # Size of Min Heap k = 3 FirstKelements(arr, size, k) '''Code is written by Rajat Kumar.....'''
C#
using System;
using System.Collections.Generic;
public class GFG
{
public static void FirstKelements(int []arr,
int size,
int k)
{
// Creating Min Heap for given
// array with only k elements
// Create min heap with priority queue
List<int> minHeap = new List<int>();
for(int i = 0; i < k; i++)
{
minHeap.Add(arr[i]);
}
// Loop For each element in array
// after the kth element
for(int i = k; i < size; i++)
{
minHeap.Sort();
// If current element is smaller
// than minimum ((top element of
// the minHeap) element, do nothing
// and continue to next element
if (minHeap[0] > arr[i])
continue;
// Otherwise Change minimum element
// (top element of the minHeap) to
// current element by polling out
// the top element of the minHeap
else
{
minHeap.RemoveAt(0);
minHeap.Add(arr[i]);
}
}
// Now min heap contains k maximum
// elements, Iterate and print
foreach (int i in minHeap)
{
Console.Write(i + " ");
}
}
// Driver code
public static void Main(String[] args)
{
int []arr = { 11, 3, 2, 1, 15, 5, 4,
45, 88, 96, 50, 45 };
int size = arr.Length;
// Size of Min Heap
int k = 3;
FirstKelements(arr, size, k);
}
}
// This code is contributed by aashish1995.
Javascript
<script>
function FirstKelements(arr , size , k) {
// Creating Min Heap for given
// array with only k elements
// Create min heap with priority queue
var minHeap = [];
for (var i = 0; i < k; i++) {
minHeap.push(arr[i]);
}
// Loop For each element in array
// after the kth element
for (var i = k; i < size; i++) {
minHeap.sort((a,b)=>a-b);
// If current element is smaller
// than minimum ((top element of
// the minHeap) element, do nothing
// and continue to next element
if (minHeap[minHeap.length-3] > arr[i])
continue;
// Otherwise Change minimum element
// (top element of the minHeap) to
// current element by polling out
// the top element of the minHeap
else {
minHeap.reverse();
minHeap.pop();
minHeap.reverse();
minHeap.push(arr[i]);
}
}
// Now min heap contains k maximum
// elements, Iterate and print
for (var iterator of minHeap) {
document.write(iterator + " ");
}
}
// Driver code
var arr = [11, 3, 2, 1, 15, 5, 4,
45, 88, 96, 50, 45];
var size = arr.length;
// Size of Min Heap
var k = 3;
FirstKelements(arr, size, k);
// This code is contributed by gauravrajput1
</script>
Producción
50 88 96
Complejidad temporal: O(nlogn)
Espacio auxiliar: O(n)
Método 7 (usando el algoritmo de partición Quick Sort):
- Elija un número de pivote.
- si K es menor que pivot_Index, repita el paso.
- if K == pivot_Index : Imprime la array (low to pivot para obtener K elementos más pequeños y (n-pivot_Index) a n para K elementos más grandes)
- si K > pivot_Index: repita los pasos para la parte derecha.
Podemos mejorar el algoritmo de clasificación rápida estándar mediante el uso de la función random(). En lugar de usar el elemento pivote como último elemento, podemos elegir aleatoriamente el elemento pivote. La complejidad de tiempo en el peor de los casos de esta versión es O(n2) y la complejidad de tiempo promedio es O(n).
A continuación se muestra la implementación del algoritmo anterior:
C++
#include <bits/stdc++.h>
using namespace std;
// picks up last element between start and end
int findPivot(int a[], int start, int end)
{
// Selecting the pivot element
int pivot = a[end];
// Initially partition-index will be at starting
int pIndex = start;
for (int i = start; i < end; i++) {
// If an element is lesser than pivot, swap it.
if (a[i] <= pivot) {
swap(a[i], a[pIndex]);
// Incrementing pIndex for further swapping.
pIndex++;
}
}
// Lastly swapping or the correct position of pivot
swap(a[pIndex], a[end]);
return pIndex;
}
// THIS PART OF CODE IS CONTRIBUTED BY - rjrachit
// Picks up random pivot element between start and end
int findRandomPivot(int arr[], int start, int end)
{
int n = end - start + 1;
// Selecting the random pivot index
int pivotInd = random() % n;
swap(arr[end], arr[start + pivotInd]);
int pivot = arr[end];
// initialising pivoting point to start index
pivotInd = start;
for (int i = start; i < end; i++) {
// If an element is lesser than pivot, swap it.
if (arr[i] <= pivot) {
swap(arr[i], arr[pivotInd]);
// Incrementing pivotIndex for further swapping.
pivotInd++;
}
}
// Lastly swapping or the correct position of pivot
swap(arr[pivotInd], arr[end]);
return pivotInd;
}
// THIS PART OF CODE IS CONTRIBUTED BY - rjrachit
void SmallestLargest(int a[], int low, int high, int k,
int n)
{
if (low == high)
return;
else {
int pivotIndex = findRandomPivot(a, low, high);
if (k == pivotIndex) {
cout << k << " smallest elements are : ";
for (int i = 0; i < pivotIndex; i++)
cout << a[i] << " ";
cout << endl;
cout << k << " largest elements are : ";
for (int i = (n - pivotIndex); i < n; i++)
cout << a[i] << " ";
}
else if (k < pivotIndex)
SmallestLargest(a, low, pivotIndex - 1, k, n);
else if (k > pivotIndex)
SmallestLargest(a, pivotIndex + 1, high, k, n);
}
}
// Driver Code
int main()
{
int a[] = { 11, 3, 2, 1, 15, 5, 4, 45, 88, 96, 50, 45 };
int n = sizeof(a) / sizeof(a[0]);
int low = 0;
int high = n - 1;
// Lets assume k is 3
int k = 3;
// Function Call
SmallestLargest(a, low, high, k, n);
return 0;
}
// This code is contributed by Sania Kumari Gupta
C
#include <stdio.h>
#include <stdlib.h>
// This function swaps values pointed by xp and yp
void swap(int* xp, int* yp)
{
int temp = *xp;
*xp = *yp;
*yp = temp;
}
// picks up last element between start and end
int findPivot(int a[], int start, int end)
{
// Selecting the pivot element
int pivot = a[end];
// Initially partition-index will be at starting
int pIndex = start;
for (int i = start; i < end; i++) {
// If an element is lesser than pivot, swap it.
if (a[i] <= pivot) {
swap(&a[i], &a[pIndex]);
// Incrementing pIndex for further swapping.
pIndex++;
}
}
// Lastly swapping or the correct position of pivot
swap(&a[pIndex], &a[end]);
return pIndex;
}
// THIS PART OF CODE IS CONTRIBUTED BY - rjrachit
// Picks up random pivot element between start and end
int findRandomPivot(int arr[], int start, int end)
{
int n = end - start + 1;
// Selecting the random pivot index
int pivotInd = random() % n;
swap(&arr[end], &arr[start + pivotInd]);
int pivot = arr[end];
// initialising pivoting point to start index
pivotInd = start;
for (int i = start; i < end; i++) {
// If an element is lesser than pivot, swap it.
if (arr[i] <= pivot) {
swap(&arr[i], &arr[pivotInd]);
// Incrementing pivotIndex for further swapping.
pivotInd++;
}
}
// Lastly swapping or the correct position of pivot
swap(&arr[pivotInd], &arr[end]);
return pivotInd;
}
// THIS PART OF CODE IS CONTRIBUTED BY - rjrachit
void SmallestLargest(int a[], int low, int high, int k,
int n)
{
if (low == high)
return;
else {
int pivotIndex = findRandomPivot(a, low, high);
if (k == pivotIndex) {
printf("%d smallest elements are : ", k);
for (int i = 0; i < pivotIndex; i++)
printf("%d ", a[i]);
printf("\n");
printf("%d largest elements are : ", k);
for (int i = (n - pivotIndex); i < n; i++)
printf("%d ", a[i]);
}
else if (k < pivotIndex)
SmallestLargest(a, low, pivotIndex - 1, k, n);
else if (k > pivotIndex)
SmallestLargest(a, pivotIndex + 1, high, k, n);
}
}
// Driver Code
int main()
{
int a[] = { 11, 3, 2, 1, 15, 5, 4, 45, 88, 96, 50, 45 };
int n = sizeof(a) / sizeof(a[0]);
int low = 0;
int high = n - 1;
// Lets assume k is 3
int k = 3;
// Function Call
SmallestLargest(a, low, high, k, n);
return 0;
}
// This code is contributed by Sania Kumari Gupta
Java
import java.util.*;
class GFG{
//picks up last element between start and end
static int findPivot(int a[], int start, int end)
{
// Selecting the pivot element
int pivot = a[end];
// Initially partition-index will be
// at starting
int pIndex = start;
for (int i = start; i < end; i++) {
// If an element is lesser than pivot, swap it.
if (a[i] <= pivot) {
int temp =a[i];
a[i]= a[pIndex];
a[pIndex] = temp;
// Incrementing pIndex for further
// swapping.
pIndex++;
}
}
// Lastly swapping or the
// correct position of pivot
int temp = a[pIndex];
a[pIndex] = a[end];
a[end] = temp;
return pIndex;
}
//THIS PART OF CODE IS CONTRIBUTED BY - rjrachit
//Picks up random pivot element between start and end
static int findRandomPivot(int arr[], int start, int end)
{
int n = end - start + 1;
// Selecting the random pivot index
int pivotInd = (int) ((Math.random()*1000000)%n);
int temp = arr[end];
arr[end] = arr[start+pivotInd];
arr[start+pivotInd] = temp;
int pivot = arr[end];
//initialising pivoting point to start index
pivotInd = start;
for (int i = start; i < end; i++) {
// If an element is lesser than pivot, swap it.
if (arr[i] <= pivot) {
int temp1 = arr[i];
arr[i]= arr[pivotInd];
arr[pivotInd] = temp1;
// Incrementing pivotIndex for further
// swapping.
pivotInd++;
}
}
// Lastly swapping or the
// correct position of pivot
int tep = arr[pivotInd];
arr[pivotInd] = arr[end];
arr[end] = tep;
return pivotInd;
}
//THIS PART OF CODE IS CONTRIBUTED BY - rjrachit
static void SmallestLargest(int a[], int low, int high, int k,
int n)
{
if (low == high)
return;
else {
int pivotIndex = findRandomPivot(a, low, high);
if (k == pivotIndex) {
System.out.print(k+ " smallest elements are : ");
for (int i = 0; i < pivotIndex; i++)
System.out.print(a[i]+ " ");
System.out.println();
System.out.print(k+ " largest elements are : ");
for (int i = (n - pivotIndex); i < n; i++)
System.out.print(a[i]+ " ");
}
else if (k < pivotIndex)
SmallestLargest(a, low, pivotIndex - 1, k, n);
else if (k > pivotIndex)
SmallestLargest(a, pivotIndex + 1, high, k, n);
}
}
// Driver Code
public static void main(String[] args)
{
int a[] = { 11, 3, 2, 1, 15, 5, 4, 45, 88, 96, 50, 45 };
int n = a.length;
int low = 0;
int high = n - 1;
// Lets assume k is 3
int k = 3;
// Function Call
SmallestLargest(a, low, high, k, n);
}
}
// This code is contributed by Rajput-Ji
Python3
# Python program to implement above approach # picks up last element between start and end import random def findPivot(a, start, end): # Selecting the pivot element pivot = a[end] # Initially partition-index will be # at starting pIndex = start for i in range(start,end): # If an element is lesser than pivot, swap it. if (a[i] <= pivot): a[i],a[pIndex] = a[pIndex],a[i] # Incrementing pIndex for further # swapping. pIndex += 1 # Lastly swapping or the # correct position of pivot a[end],a[pIndex] = a[pIndex],a[end] return pIndex #THIS PART OF CODE IS CONTRIBUTED BY - rjrachit #Picks up random pivot element between start and end def findRandomPivot(arr, start, end): n = end - start + 1 # Selecting the random pivot index pivotInd = (int((random.random()*1000000))%n) arr[end],arr[start+pivotInd] = arr[start+pivotInd],arr[end] pivot = arr[end] #initialising pivoting poto start index pivotInd = start for i in range(start,end): # If an element is lesser than pivot, swap it. if (arr[i] <= pivot): arr[i],arr[pivotInd] = arr[pivotInd],arr[i] # Incrementing pivotIndex for further # swapping. pivotInd += 1 # Lastly swapping or the # correct position of pivot arr[pivotInd],arr[end] = arr[end],arr[pivotInd] return pivotInd def SmallestLargest(a, low, high, k, n): if (low == high): return else: pivotIndex = findRandomPivot(a, low, high) if (k == pivotIndex): print(str(k)+ " smallest elements are :",end=" ") for i in range(pivotIndex): print(a[i],end = " ") print() print(str(k)+ " largest elements are :",end=" ") for i in range(n - pivotIndex,n): print(a[i],end=" ") elif (k < pivotIndex): SmallestLargest(a, low, pivotIndex - 1, k, n) elif (k > pivotIndex): SmallestLargest(a, pivotIndex + 1, high, k, n) # Driver code a = [ 11, 3, 2, 1, 15, 5, 4, 45, 88, 96, 50, 45 ] n = len(a) low = 0 high = n - 1 # assume k is 3 k = 3 # Function Call SmallestLargest(a, low, high, k, n) # This code is contributed by shinjanpatra
C#
using System;
using System.Text;
public class GFG {
// picks up last element between start and end
static int findPivot(int []a, int start, int end) {
// Selecting the pivot element
int pivot = a[end];
// Initially partition-index will be
// at starting
int pIndex = start;
for (int i = start; i < end; i++) {
// If an element is lesser than pivot, swap it.
if (a[i] <= pivot) {
int temp6 = a[i];
a[i] = a[pIndex];
a[pIndex] = temp6;
// Incrementing pIndex for further
// swapping.
pIndex++;
}
}
// Lastly swapping or the
// correct position of pivot
int temp = a[pIndex];
a[pIndex] = a[end];
a[end] = temp;
return pIndex;
}
// THIS PART OF CODE IS CONTRIBUTED BY - rjrachit
// Picks up random pivot element between start and end
static int findRandomPivot(int []arr, int start, int end) {
int n = end - start + 1;
// Selecting the random pivot index
Random _random = new Random();
var randomNumber = _random.Next(0, n);
int pivotInd = randomNumber;
int temp = arr[end];
arr[end] = arr[start + pivotInd];
arr[start + pivotInd] = temp;
int pivot = arr[end];
// initialising pivoting point to start index
pivotInd = start;
for (int i = start; i < end; i++) {
// If an element is lesser than pivot, swap it.
if (arr[i] <= pivot) {
int temp1 = arr[i];
arr[i] = arr[pivotInd];
arr[pivotInd] = temp1;
// Incrementing pivotIndex for further
// swapping.
pivotInd++;
}
}
// Lastly swapping or the
// correct position of pivot
int tep = arr[pivotInd];
arr[pivotInd] = arr[end];
arr[end] = tep;
return pivotInd;
}
static void SmallestLargest(int []a, int low, int high, int k, int n) {
if (low == high)
return;
else {
int pivotIndex = findRandomPivot(a, low, high);
if (k == pivotIndex) {
Console.Write(k + " smallest elements are : ");
for (int i = 0; i < pivotIndex; i++)
Console.Write(a[i] + " ");
Console.WriteLine();
Console.Write(k + " largest elements are : ");
for (int i = (n - pivotIndex); i < n; i++)
Console.Write(a[i] + " ");
}
else if (k < pivotIndex)
SmallestLargest(a, low, pivotIndex - 1, k, n);
else if (k > pivotIndex)
SmallestLargest(a, pivotIndex + 1, high, k, n);
}
}
// Driver Code
public static void Main(String[] args) {
int []a = { 11, 3, 2, 1, 15, 5, 4, 45, 88, 96, 50, 45 };
int n = a.Length;
int low = 0;
int high = n - 1;
// Lets assume k is 3
int k = 3;
// Function Call
SmallestLargest(a, low, high, k, n);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript code to implement the approach
//picks up last element between start and end
function findPivot( a, start, end)
{
// Selecting the pivot element
let pivot = a[end];
// Initially partition-index will be
// at starting
let pIndex = start;
for (let i = start; i < end; i++) {
// If an element is lesser than pivot, swap it.
if (a[i] <= pivot) {
let temp =a[i];
a[i]= a[pIndex];
a[pIndex] = temp;
// Incrementing pIndex for further
// swapping.
pIndex++;
}
}
// Lastly swapping or the
// correct position of pivot
let temp = a[pIndex];
a[pIndex] = a[end];
a[end] = temp;
return pIndex;
}
//THIS PART OF CODE IS CONTRIBUTED BY - rjrachit
//Picks up random pivot element between start and end
function findRandomPivot(arr, start, end)
{
let n = end - start + 1;
// Selecting the random pivot index
let pivotInd = (parseInt((Math.random()*1000000))%n);
let temp = arr[end];
arr[end] = arr[start+pivotInd];
arr[start+pivotInd] = temp;
let pivot = arr[end];
//initialising pivoting point to start index
pivotInd = start;
for (let i = start; i < end; i++) {
// If an element is lesser than pivot, swap it.
if (arr[i] <= pivot) {
let temp1 = arr[i];
arr[i]= arr[pivotInd];
arr[pivotInd] = temp1;
// Incrementing pivotIndex for further
// swapping.
pivotInd++;
}
}
// Lastly swapping or the
// correct position of pivot
let tep = arr[pivotInd];
arr[pivotInd] = arr[end];
arr[end] = tep;
return pivotInd;
}
//THIS PART OF CODE IS CONTRIBUTED BY - rjrachit
function SmallestLargest( a, low, high, k,
n)
{
if (low == high)
return;
else {
let pivotIndex = findRandomPivot(a, low, high);
if (k == pivotIndex) {
document.write(k+ " smallest elements are : ");
for (let i = 0; i < pivotIndex; i++)
document.write(a[i]+ " ");
document.write("<br/>");
document.write(k+ " largest elements are : ");
for (let i = (n - pivotIndex); i < n; i++)
document.write(a[i]+ " ");
}
else if (k < pivotIndex)
SmallestLargest(a, low, pivotIndex - 1, k, n);
else if (k > pivotIndex)
SmallestLargest(a, pivotIndex + 1, high, k, n);
}
}
// Driver code
let a = [ 11, 3, 2, 1, 15, 5, 4, 45, 88, 96, 50, 45 ];
let n = a.length;
let low = 0;
let high = n - 1;
// Lets assume k is 3
let k = 3;
// Function Call
SmallestLargest(a, low, high, k, n);
// This code is contributed by sanjoy_62.
</script>
Producción
3 smallest elements are : 3 2 1 3 largest elements are : 96 50 88
Complejidad de tiempo: O(nlogn)
Espacio auxiliar: O(1)
Método 8 (usando la biblioteca STL de la cola de prioridad):
en este enfoque, podemos imprimir de manera eficiente los k elementos más grandes/más pequeños de una array usando una cola de prioridad en una complejidad de tiempo O (n * log (k)) . Primero, empujamos k elementos a la cola de prioridad desde la array. A partir de ahí, después de cada inserción de un elemento de array, mostraremos el elemento en la parte superior de la cola de prioridad . En el caso del k elemento más grande, la cola de prioridad estará en orden creciente y, por lo tanto, el elemento más alto será el más pequeño, por lo que lo eliminaremos. De manera similar, en el caso del k elemento más pequeño, la cola de prioridad está enorden decreciente y, por lo tanto, el elemento superior es el más grande, por lo que lo eliminaremos. De esta manera se recorre toda la array y se imprime la cola de prioridad de tamaño k que contiene k elementos más grandes/más pequeños.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code for k largest/ smallest elements in an array
#include <bits/stdc++.h>
using namespace std;
// Function to find k largest array element
void kLargest(vector<int>& v, int N, int K)
{
// Implementation using
// a Priority Queue
priority_queue<int, vector<int>, greater<int> >pq;
for (int i = 0; i < N; ++i) {
// Insert elements into
// the priority queue
pq.push(v[i]);
// If size of the priority
// queue exceeds k
if (pq.size() > K) {
pq.pop();
}
}
// Print the k largest element
while(!pq.empty())
{
cout << pq.top() <<" ";
pq.pop();
}
cout<<endl;
}
// Function to find k smallest array element
void kSmalest(vector<int>& v, int N, int K)
{
// Implementation using
// a Priority Queue
priority_queue<int> pq;
for (int i = 0; i < N; ++i) {
// Insert elements into
// the priority queue
pq.push(v[i]);
// If size of the priority
// queue exceeds k
if (pq.size() > K) {
pq.pop();
}
}
// Print the k smallest element
while(!pq.empty())
{
cout << pq.top() <<" ";
pq.pop();
}
}
// driver program
int main()
{
// Given array
vector<int> arr = { 11, 3, 2, 1, 15, 5, 4, 45, 88, 96, 50, 45 };
// Size of array
int n = arr.size();
int k = 3;
cout<<k<<" largest elements are : ";
kLargest(arr, n, k);
cout<<k<<" smallest elements are : ";
kSmalest(arr, n, k);
}
// This code is contributed by Pushpesh Raj.
Java
// Java code for k largest/ smallest elements in an array
import java.util.*;
class GFG {
// Function to find k largest array element
static void kLargest(int a[], int n, int k)
{
// Implementation using
// a Priority Queue
PriorityQueue<Integer> pq
= new PriorityQueue<Integer>();
for (int i = 0; i < n; ++i) {
// Insert elements into
// the priority queue
pq.add(a[i]);
// If size of the priority
// queue exceeds k
if (pq.size() > k) {
pq.poll();
}
}
// Print the k largest element
while (!pq.isEmpty()) {
System.out.print(pq.peek() + " ");
pq.poll();
}
System.out.println();
}
// Function to find k smallest array element
static void kSmallest(int a[], int n, int k)
{
// Implementation using
// a Priority Queue
PriorityQueue<Integer> pq
= new PriorityQueue<Integer>(
Collections.reverseOrder());
for (int i = 0; i < n; ++i) {
// Insert elements into
// the priority queue
pq.add(a[i]);
// If size of the priority
// queue exceeds k
if (pq.size() > k) {
pq.poll();
}
}
// Print the k largest element
while (!pq.isEmpty()) {
System.out.print(pq.peek() + " ");
pq.poll();
}
}
// Driver Code
public static void main(String[] args)
{
int a[]
= { 11, 3, 2, 1, 15, 5, 4, 45, 88, 96, 50, 45 };
int n = a.length;
int k = 3;
System.out.print(k + " largest elements are : ");
// Function Call
kLargest(a, n, k);
System.out.print(k + " smallest elements are : ");
// Function Call
kSmallest(a, n, k);
}
}
// This code is contributed by Aarti_Rathi
Python3
# Python code for k largest/ smallest elements in an array import heapq # Function to find k largest array element def kLargest(v, N, K): # Implementation using # a Priority Queue pq = [] heapq.heapify(pq) for i in range(N): # Insert elements into # the priority queue heapq.heappush(pq, v[i]) # If size of the priority # queue exceeds k if (len(pq) > K): heapq.heappop(pq) # Print the k largest element while(len(pq) != 0): print(heapq.heappop(pq), end=' ') print() # Function to find k smallest array element def kSmalest(v, N, K): # Implementation using # a Priority Queue pq = [] for i in range(N): # Insert elements into # the priority queue heapq.heappush(pq, -1*v[i]) # If size of the priority # queue exceeds k if (len(pq) > K): heapq.heappop(pq) # Print the k largest element while(len(pq) != 0): print(heapq.heappop(pq)*-1, end=' ') print() # driver program # Given array arr = [11, 3, 2, 1, 15, 5, 4, 45, 88, 96, 50, 45] # Size of array n = len(arr) k = 3 print(k, " largest elements are : ", end='') kLargest(arr, n, k) print(k, " smallest elements are : ", end='') kSmalest(arr, n, k) # This code is contributed by Abhijeet Kumar(abhijeet19403)
Producción
3 largest elements are : 50 88 96 3 smallest elements are : 3 2 1
Complejidad de tiempo: O(n*log(k))
Espacio auxiliar: O(k)
Escriba comentarios si encuentra incorrecta alguna de las explicaciones/algoritmos anteriores, o encuentra mejores formas de resolver el mismo problema.
Referencias:
http://en.wikipedia.org/wiki/Selection_algorithm
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA