K-й наименьший или наибольший элемент в несортированном массиве | Комплект 4

Опубликовано: 5 Января, 2022

Для массива arr [] и числа K , где K меньше размера массива, нам нужно найти K-й наименьший элемент в данном массиве. Предусмотрено, что элементы массива могут повторяться (не ограничиваясь отдельными).

Примеры:

Input: arr[] = {7, 10, 4, 3, 20, 15}, K = 3 
Output: 7

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

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Мы обсудили эту статью и с другими подходами:

  • K-й наименьший / наибольший элемент в несортированном массиве | Комплект 1
  • K-й наименьший / наибольший элемент в несортированном массиве | Установите 2 (Ожидаемое линейное время)
  • K-й наименьший / наибольший элемент в несортированном массиве | Установите 3 (линейное время наихудшего случая)

Подход: идея состоит в том, чтобы использовать концепцию подсчетной сортировки. Ниже приведены шаги:

  1. Найдите максимальный элемент (скажем, maxE ) в массиве и создайте массив (скажем, freq [] ) длины maxE + 1 и инициализируйте его нулем.
  2. Перебрать все элементы в данном массиве и сохранить частоту элемента в freq [] .
  3. Перебираем массив freq [], пока не дойдем до K-го элемента.
  4. Выведите K-й элемент, достигнутый на предыдущем шаге.

Ниже представлена реализация описанного выше подхода:

C ++

// 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];
}
// Frequenncy 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];
}
// Frequenncy 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

# 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]
# Frequenncy 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 #

// 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];
}
// Frequenncy 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

Javascript

<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];
}
// Frequenncy 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

Сложность по времени: O (N), где N - количество элементов в данном массиве.
Вспомогательное пространство: O (M), где M - максимальный элемент в данном массиве.

Статьи

РЕКОМЕНДУЕМЫЕ СТАТЬИ

Новые возможности для программистов на крипторынке
5 Мая, 2024
Интеграция с внешними сервисами и API на Битрикс
1 Мая, 2024
Эффективное обучение и доработка CRM в Битрикс24: ключевые моменты для бизнеса
28 Апреля, 2024
Онлайн-обменники: быстрый и удобный способ конвертации активов в современном мире
17 Апреля, 2024
Лучшие онлайн-курсы по WordPress: рейтинг 2024
29 Марта, 2024
Для кого буду полезны услуги SMS-центра
24 Марта, 2024
Что такое экспертиза исходного кода и как ее проводят?
3 Марта, 2024
Как добавить деньги на счет аккаунта Steam через криптовалюту
20 Февраля, 2024