Рубрики

K'th самый маленький / самый большой элемент в несортированном массиве | Комплект 1

Для данного массива и числа k, где k меньше размера массива, нам нужно найти k-й наименьший элемент в данном массиве. Дано, что все элементы массива различны.

Примеры:

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

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

Мы обсудили аналогичную проблему для печати k крупнейших элементов .

Способ 1 (простое решение)
Простым решением является сортировка заданного массива с помощью алгоритма сортировки O (N log N), такого как Merge Sort , Heap Sort и т. Д., И возврат элемента с индексом k-1 в отсортированный массив.

Сложность времени этого решения O (N Log N)

C ++

// Простая программа на C ++ для поиска k-го наименьшего элемента
#include<iostream>
#include<algorithm>

using namespace std;

  
// Функция для возврата k-го наименьшего элемента в данном массиве

int kthSmallest(int arr[], int n, int k)

{

    // Сортировать указанный массив

    sort(arr, arr+n);

  

    // Возвращаем k-й элемент в отсортированный массив

    return arr[k-1];

}

  
// Программа драйвера для тестирования вышеуказанных методов

int main()

{

    int arr[] = {12, 3, 5, 7, 19};

    int n = sizeof(arr)/sizeof(arr[0]), k = 2;

    cout << "K'th smallest element is " <<  kthSmallest(arr, n, k);

    return 0;

}

Джава

// Java-код для k-го наименьшего элемента
// в массиве

import java.util.Arrays;

import java.util.Collections;

  

class GFG

{   

    // Функция для возврата k 'самого маленького

    // элемент в данном массиве

    public static int kthSmallest(Integer [] arr, 

                                         int k) 

    {

        // Сортировать указанный массив

        Arrays.sort(arr);

  

        // Возвращаем k-й элемент в

        // отсортированный массив

        return arr[k-1];

    

      

    // драйверная программа

    public static void main(String[] args) 

    {

        Integer arr[] = new Integer[]{12, 3, 5, 7, 19};

        int k = 2;

        System.out.print( "K'th smallest element is "+

                            kthSmallest(arr, k) );     

    }

}

  
// Этот код предоставлен Чхави

python3

# Python3 программа для поиска k
# элемент

  
# Функция для возврата k 'самого маленького
# элемент в данном массиве

def kthSmallest(arr, n, k):

  

    # Сортировать указанный массив

    arr.sort()

  

    # Вернуть k-й элемент в

    # отсортированный массив

    return arr[k-1]

  
# Код драйвера

if __name__=='__main__':

    arr = [12, 3, 5, 7, 19]

    n = len(arr)

    k = 2

    print("K'th smallest element is",

          kthSmallest(arr, n, k))

  
# Этот код предоставлен
# Shrikant13

C #

// код C # для k-го наименьшего элемента
// в массиве

using System;

  

class GFG { 

      

    // Функция для возврата k 'самого маленького

    // элемент в данном массиве

    public static int kthSmallest(int []arr, 

                                      int k) 

    {

          

        // Сортировать указанный массив

        Array.Sort(arr);

  

        // Возвращаем k-й элемент в

        // отсортированный массив

        return arr[k-1];

    

      

    // драйверная программа

    public static void Main() 

    {

        int []arr = new int[]{12, 3, 5, 

                                  7, 19};

        int k = 2;

        Console.Write( "K'th smallest element"

              + " is "+ kthSmallest(arr, k) );     

    }

}

  
// Этот код предоставлен нитин митталь.

PHP

<?php
// Простая PHP-программа для поиска
// k 'самый маленький элемент

  
// Функция для возврата k 'самого маленького
// элемент в данном массиве

function kthSmallest($arr, $n, $k)

{

      

    // Сортировать указанный массив

    sort($arr);

  

    // Возвращаем k-й элемент

    // в отсортированном массиве

    return $arr[$k - 1];

}

  

    // Код драйвера

    $arr = array(12, 3, 5, 7, 19);

    $n =count($arr);

    $k = 2;

    echo "K'th smallest element is "

       , kthSmallest($arr, $n, $k);

  
// Этот код предоставлен anuj_67.
?>


Выход:

K'th smallest element is 5 

Метод 2 (Использование Min Heap — HeapSelect)
Мы можем найти k-й наименьший элемент во временной сложности лучше, чем O (N Log N). Простая опция заключается в создании Min Heap из заданных n элементов и вызове extractMin () k раз.

Ниже приведена реализация C ++ вышеуказанного метода.

// Программа на C ++ для поиска k-го наименьшего элемента с использованием min heap
#include<iostream>
#include<climits>

using namespace std;

  
// Прототип служебной функции для замены двух целых чисел

void swap(int *x, int *y);

  
// Класс для Min Heap

class MinHeap

{

    int *harr; // указатель на массив элементов в куче

    int capacity; // максимально возможный размер кучи min

    int heap_size; // Текущее количество элементов в мин куче

public:

    MinHeap(int a[], int size); // Конструктор

    void MinHeapify(int i);  // Чтобы минимизировать поддерево с корнем из индекса i

    int parent(int i) { return (i-1)/2; }

    int left(int i) { return (2*i + 1); }

    int right(int i) { return (2*i + 2); }

  

    int extractMin();  // извлекает корневой (минимальный) элемент

    int getMin() { return harr[0]; } // Возвращает минимум

};

  

MinHeap::MinHeap(int a[], int size)

{

    heap_size = size;

    harr = a;  // сохранить адрес массива

    int i = (heap_size - 1)/2;

    while (i >= 0)

    {

        MinHeapify(i);

        i--;

    }

}

  
// Метод удаления минимального элемента (или корня) из минимальной кучи

int MinHeap::extractMin()

{

    if (heap_size == 0)

        return INT_MAX;

  

    // Сохраняем минимальное вакуе.

    int root = harr[0];

  

    // Если есть более 1 элементов, переместить последний элемент в корень

    // и вызываем heapify.

    if (heap_size > 1)

    {

        harr[0] = harr[heap_size-1];

        MinHeapify(0);

    }

    heap_size--;

  

    return root;

}

  
// Рекурсивный метод, чтобы накапливать поддерево с корнем по заданному индексу
// Этот метод предполагает, что поддеревья уже сложены

void MinHeap::MinHeapify(int i)

{

    int l = left(i);

    int r = right(i);

    int smallest = i;

    if (l < heap_size && harr[l] < harr[i])

        smallest = l;

    if (r < heap_size && harr[r] < harr[smallest])

        smallest = r;

    if (smallest != i)

    {

        swap(&harr[i], &harr[smallest]);

        MinHeapify(smallest);

    }

}

  
// Утилита для замены двух элементов

void swap(int *x, int *y)

{

    int temp = *x;

    *x = *y;

    *y = temp;

}

  
// Функция для возврата k-го наименьшего элемента в данном массиве

int kthSmallest(int arr[], int n, int k)

{

    // Создаем кучу из n элементов: O (n) time

    MinHeap mh(arr, n);

  

    // Извлекаем мин (к-1) раз

    for (int i=0; i<k-1; i++)

        mh.extractMin();

  

    // Возвращаем корень

    return mh.getMin();

}

  
// Программа драйвера для тестирования вышеуказанных методов

int main()

{

    int arr[] = {12, 3, 5, 7, 19};

    int n = sizeof(arr)/sizeof(arr[0]), k = 2;

    cout << "K'th smallest element is " << kthSmallest(arr, n, k);

    return 0;

}

Выход:

K'th smallest element is 5 

Временная сложность этого решения составляет O (n + kLogn).

Метод 3 (с использованием Max-Heap)
Мы также можем использовать Max Heap для поиска k-го наименьшего элемента. Ниже приводится алгоритм.
1) Построить MH Max-Heap из первых k элементов (от arr [0] до arr [k-1]) данного массива. Ok)

2) Для каждого элемента, после k-го элемента (от arr [k] до arr [n-1]), сравните его с корнем MH.
…… а) Если элемент меньше корневого, сделайте его корневым и вызовите heapify для MH
…… б) Остальное игнорируй.
// Шаг 2 — это O ((nk) * logk)

3) Наконец, корень MH является k-м наименьшим элементом.

Временная сложность этого решения составляет O (k + (nk) * Logk)

Ниже приведена реализация вышеописанного алгоритма на C ++.

// Программа на C ++ для поиска k-го наименьшего элемента с использованием max heap
#include<iostream>
#include<climits>

using namespace std;

  
// Прототип служебной функции для замены двух целых чисел

void swap(int *x, int *y);

  
// Класс для Max Heap

class MaxHeap

{

    int *harr; // указатель на массив элементов в куче

    int capacity; // максимально возможный размер кучи

    int heap_size; // Текущее количество элементов в максимальной куче

public:

    MaxHeap(int a[], int size); // Конструктор

    void maxHeapify(int i);  // Чтобы maxHeapify поддерево укоренилось с индексом i

    int parent(int i) { return (i-1)/2; }

    int left(int i) { return (2*i + 1); }

    int right(int i) { return (2*i + 2); }

  

    int extractMax();  // извлекает корневой (максимальный) элемент

    int getMax() { return harr[0]; } // Возвращает максимум

  

    // заменить корень новым узлом x и heapify () новым корнем

    void replaceMax(int x) { harr[0] = x;  maxHeapify(0); }

};

  

MaxHeap::MaxHeap(int a[], int size)

{

    heap_size = size;

    harr = a;  // сохранить адрес массива

    int i = (heap_size - 1)/2;

    while (i >= 0)

    {

        maxHeapify(i);

        i--;

    }

}

  
// Метод удаления максимального элемента (или корня) из максимальной кучи

int MaxHeap::extractMax()

{

    if (heap_size == 0)

        return INT_MAX;

  

    // Сохраняем максимальный вакуе.

    int root = harr[0];

  

    // Если есть более 1 элементов, переместить последний элемент в корень

    // и вызываем heapify.

    if (heap_size > 1)

    {

        harr[0] = harr[heap_size-1];

        maxHeapify(0);

    }

    heap_size--;

  

    return root;

}

  
// Рекурсивный метод, чтобы накапливать поддерево с корнем по заданному индексу
// Этот метод предполагает, что поддеревья уже сложены

void MaxHeap::maxHeapify(int i)

{

    int l = left(i);

    int r = right(i);

    int largest = i;

    if (l < heap_size && harr[l] > harr[i])

        largest = l;

    if (r < heap_size && harr[r] > harr[largest])

        largest = r;

    if (largest != i)

    {

        swap(&harr[i], &harr[largest]);

        maxHeapify(largest);

    }

}

  
// Утилита для замены двух элементов

void swap(int *x, int *y)

{

    int temp = *x;

    *x = *y;

    *y = temp;

}

  
// Функция для возврата k'ого наибольшего элемента в данном массиве

int kthSmallest(int arr[], int n, int k)

{

    // Создаем кучу первых k элементов: O (k) time

    MaxHeap mh(arr, k);

  

    // Обработка оставшихся nk элементов. Если текущий элемент

    // меньше корня, заменить корень текущим элементом

    for (int i=k; i<n; i++)

        if (arr[i] < mh.getMax())

           mh.replaceMax(arr[i]);

  

    // Возвращаем корень

    return mh.getMax();

}

  
// Программа драйвера для тестирования вышеуказанных методов

int main()

{

    int arr[] = {12, 3, 5, 7, 19};

    int n = sizeof(arr)/sizeof(arr[0]), k = 4;

    cout << "K'th smallest element is " <<  kthSmallest(arr, n, k);

    return 0;

}

Выход:

K'th smallest element is 5 

Метод 4 (Быстрый выбор)
Это оптимизация по сравнению со способом 1, если на первом этапе в качестве алгоритма сортировки используется быстрая сортировка. В QuickSort мы выбираем элемент pivot, затем перемещаем элемент pivot в его правильное положение и разделяем массив вокруг него. Идея состоит не в том, чтобы выполнить полную быструю сортировку, а в том, чтобы остановиться в точке, где сам шарнир является k-мельчайшим элементом. Кроме того, не повторять для левой и правой сторон оси, но повторять для одной из них в соответствии с положением оси. Наихудшая временная сложность этого метода — O (n 2 ), но в среднем он работает за O (n).

C ++

#include<iostream>
#include<climits>

using namespace std;

  

int partition(int arr[], int l, int r);

  
// Эта функция возвращает k 'самый маленький элемент в arr [l..r], используя
// Метод быстрой сортировки. Предположение: все элементы в ARR [] различны

int kthSmallest(int arr[], int l, int r, int k)

{

    // Если k меньше количества элементов в массиве

    if (k > 0 && k <= r - l + 1)

    {

        // Разделим массив вокруг последнего элемента и получаем

        // положение элемента pivot в отсортированном массиве

        int pos = partition(arr, l, r);

  

        // Если позиция совпадает с k

        if (pos-l == k-1)

            return arr[pos];

        if (pos-l > k-1)  // Если позиция больше, повторить для левого подмассива

            return kthSmallest(arr, l, pos-1, k);

  

        // Остальное повторяется для правого подмассива

        return kthSmallest(arr, pos+1, r, k-pos+l-1);

    }

  

    // Если k больше чем количество элементов в массиве

    return INT_MAX;

}

  

void swap(int *a, int *b)

{

    int temp = *a;

    *a = *b;

    *b = temp;

}

  
// Стандартный процесс разбиения QuickSort (). Считает последний
// элемент как опорный элемент и перемещает все меньшие элементы слева от него
// и больше элементов справа

int partition(int arr[], int l, int r)

{

    int x = arr[r], i = l;

    for (int j = l; j <= r - 1; j++)

    {

        if (arr[j] <= x)

        {

            swap(&arr[i], &arr[j]);

            i++;

        }

    }

    swap(&arr[i], &arr[r]);

    return i;

}

  
// Программа драйвера для тестирования вышеуказанных методов

int main()

{

    int arr[] = {12, 3, 5, 7, 4, 19, 26};

    int n = sizeof(arr)/sizeof(arr[0]), k = 3;

    cout << "K'th smallest element is " << kthSmallest(arr, 0, n-1, k);

    return 0;

}

Джава

// Java-код для k-го наименьшего элемента в массиве

import java.util.Arrays;

import java.util.Collections;

  

class GFG

{  

    // Стандартный процесс разбиения QuickSort.

    // считает последний элемент опорным

    // и перемещает все меньшие элементы слева от

    // это и большие элементы справа

    public static int partition(Integer [] arr, int l, 

                                               int r)

    {

        int x = arr[r], i = l;

        for (int j = l; j <= r - 1; j++)

        {

            if (arr[j] <= x)

            {

                // Меняем местами arr [i] и arr [j]

                int temp = arr[i];

                arr[i] = arr[j];

                arr[j] = temp;

  

                i++;

            }

        }

          

        // Меняем местами arr [i] и arr [r]

        int temp = arr[i];

        arr[i] = arr[r];

        arr[r] = temp;

  

        return i;

    }

      

    // Эта функция возвращает k 'самый маленький элемент

    // в arr [l..r] используя метод QuickSort.

    // Предположение: все элементы в ARR [] различны

    public static int kthSmallest(Integer[] arr, int l, 

                                         int r, int k)

    {

        // Если k меньше количества элементов

        // в массиве

        if (k > 0 && k <= r - l + 1)

        {

            // Разделим массив вокруг последнего

            // элемент и получить позицию разворота

            // элемент в отсортированном массиве

            int pos = partition(arr, l, r);

  

            // Если позиция совпадает с k

            if (pos-l == k-1)

                return arr[pos];

              

            // Если позиция больше, повторить для

            // левый подмассив

            if (pos-l > k-1

                return kthSmallest(arr, l, pos-1, k);

  

            // Остальное повторяется для правого подмассива

            return kthSmallest(arr, pos+1, r, k-pos+l-1);

        }

  

        // Если k больше чем количество элементов

        // в массиве

        return Integer.MAX_VALUE;

    }

  

    // Программа драйвера для тестирования вышеуказанных методов

    public static void main(String[] args)

    {

        Integer arr[] = new Integer[]{12, 3, 5, 7, 4, 19, 26};

        int k = 3;

        System.out.print( "K'th smallest element is " +

                     kthSmallest(arr, 0, arr.length - 1, k) );

    }

}

  
// Этот код предоставлен Чхави

Python 3

# Эта функция возвращает самый маленький элемент
# в arr [l..r] используя метод QuickSort.
# Предположение: все элементы в ARR [] различаются

import sys

  

def kthSmallest(arr, l, r, k):

  

    # Если k меньше, чем число

    # элементов в массиве

    if (k > 0 and k <= r - l + 1):

      

        # Разделить массив вокруг последнего

        # элемент и получить позицию разворота

        # элемент в отсортированном массиве

        pos = partition(arr, l, r)

  

        # Если позиция совпадает с k

        if (pos - l == k - 1):

            return arr[pos]

        if (pos - l > k - 1): # Если позиция больше,

                              # recur для левого подмассива

            return kthSmallest(arr, l, pos - 1, k)

  

        # Остальное повторяется для правильного подмассива

        return kthSmallest(arr, pos + 1, r,

                            k - pos + l - 1)

  

    # Если k больше числа

    # элементов в массиве

    return sys.maxsize

  
# Стандартный процесс разбиения QuickSort ().
# Он рассматривает последний элемент как опору и
# перемещает все меньшие элементы слева от него
# и больше элементов справа

def partition(arr, l, r):

  

    x = arr[r]

    i = l

    for j in range(l, r):

        if (arr[j] <= x):

            arr[i], arr[j] = arr[j], arr[i]

            i += 1

    arr[i], arr[r] = arr[r], arr[i]

    return i

  
Код водителя

if __name__ == "__main__":

      

    arr = [12, 3, 5, 7, 4, 19, 26]

    n = len(arr)

    k = 3;

    print("K'th smallest element is"

           kthSmallest(arr, 0, n - 1, k))

  
# Этот код предоставлен ita_c

C #

// код C # для k-го наименьшего элемента
// в массиве

using System;

  

class GFG 

  
// Стандартный процесс разбиения QuickSort.
// считает последний элемент опорным
// и перемещает все меньшие элементы слева от
// это и большие элементы справа

public static int partition(int [] arr, 

                            int l, int r) 

    int x = arr[r], i = l;

    int temp = 0;

    for (int j = l; j <= r - 1; j++) 

    

          

        if (arr[j] <= x) 

        

            // Меняем местами arr [i] и arr [j]

            temp = arr[i]; 

            arr[i] = arr[j]; 

            arr[j] = temp; 

  

            i++; 

        

    

      

    // Меняем местами arr [i] и arr [r]

    temp = arr[i]; 

    arr[i] = arr[r]; 

    arr[r] = temp; 

  

    return i; 

  
// Эта функция возвращает k 'наименьшее
// элемент в arr [l..r] используя QuickSort
// основанный метод. Предположение: все элементы
// В ARR [] ОТЛИЧАЮТСЯ

public static int kthSmallest(int[] arr, int l, 

                                  int r, int k) 

    // Если k меньше чем число

    // элементов в массиве

    if (k > 0 && k <= r - l + 1) 

    

        // Разделим массив вокруг последнего

        // элемент и получить позицию разворота

        // элемент в отсортированном массиве

        int pos = partition(arr, l, r); 

  

        // Если позиция совпадает с k

        if (pos - l == k - 1) 

            return arr[pos]; 

          

        // Если позиция больше, повторить для

        // левый подмассив

        if (pos - l > k - 1) 

            return kthSmallest(arr, l, pos - 1, k); 

  

        // Остальное повторяется для правого подмассива

        return kthSmallest(arr, pos + 1, r,

                           k - pos + l - 1); 

    

  

    // Если k больше чем число

    // элементов в массиве

    return int.MaxValue; 

  
// Код драйвера

public static void Main() 

    int []arr = {12, 3, 5, 7, 4, 19, 26}; 

    int k = 3; 

    Console.Write( "K'th smallest element is "

            kthSmallest(arr, 0, arr.Length - 1, k)); 


  
// Этот код добавлен
// от 29AjayKumar


Выход:

K'th smallest element is 5 

Есть еще два решения, которые лучше, чем рассмотренные выше: одно решение заключается в создании рандомизированной версии quickSelect (), а другое решение — алгоритм линейного времени наихудшего случая (см. Следующие посты).

K'th самый маленький / самый большой элемент в несортированном массиве | Набор 2 (ожидаемое линейное время)
K'th самый маленький / самый большой элемент в несортированном массиве | Набор 3 (наихудший случай линейного времени)


Ссылки:

http://www.ics.uci.edu/~eppstein/161/960125.html
http://www.cs.rit.edu/~ib/Classes/CS515_Spring12-13/Slides/022-SelectMasterThm.pdf

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

K'th самый маленький / самый большой элемент в несортированном массиве | Комплект 1

0.00 (0%) 0 votes