Рубрики

k самых больших (или самых маленьких) элементов в массиве | добавлен метод Min Heap

Вопрос: Напишите эффективную программу для печати k самых больших элементов в массиве. Элементы в массиве могут быть в любом порядке.

Например, если задан массив [1, 23, 12, 9, 30, 2, 50] и вас просят указать самые большие 3 элемента, т.е. k = 3, тогда ваша программа должна вывести 50, 30 и 23.


Способ 1 (использовать Bubble k раз)

Спасибо Шайлендре за предложенный подход.
1) Измените Bubble Sort для запуска внешнего цикла не более k раз.
2) Распечатать последние k элементов массива, полученных на шаге 1.

Как и Bubble sort, другие алгоритмы сортировки, такие как Selection Sort, также могут быть изменены, чтобы получить k самых больших элементов.

Способ 2 (использовать временный массив)
K самых больших элементов из обр [0..n-1]

1) Сохраните первые k элементов во временном массиве temp [0..k-1].
2) Найдите самый маленький элемент в temp [], пусть самый маленький элемент будет min .
3-а) Для каждого элемента x из arr [k] в arr [n-1]. О (пк)
Если x больше min, тогда удалите min из temp [] и вставьте x .
3-б) Затем определите новый минимум из temp []. Ok)
4) Вывести последние k элементов temp []

Сложность времени: O ((nk) * k). Если мы хотим отсортировать вывод, то O ((nk) * k + klogk)

Спасибо nesamani1822 за предложение этого метода.

Метод 3 (использовать сортировку)
1) Сортировка элементов по убыванию в O (nLogn)
2) Вывести первые k чисел из отсортированного массива O (k).
Ниже приводится реализация выше.

C ++

// C ++ код для k самых больших элементов в массиве
#include <bits/stdc++.h>

using namespace std;

  

void kLargest(int arr[], int n, int k)

{

    // Сортировка заданного массива в обратном порядке

    // заказ.

    sort(arr, arr + n, greater<int>());

  

    // Распечатать первый k-й по величине элемент

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

        cout << arr[i] << " ";

}

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

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);

}

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

Джава

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

import java.util.Arrays;

import java.util.Collections;

  

class GFG {

    public static void kLargest(Integer[] arr, int k)

    {

        // Сортировка указанного массива arr в обратном порядке

        // Этот метод не работает с примитивными данными

        // типы. Итак, вместо int, целочисленный тип

        // массив будет использоваться

        Arrays.sort(arr, Collections.reverseOrder());

  

        // Распечатать первый k-й по величине элемент

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

            System.out.print(arr[i] + " ");

    }

  

    public static void main(String[] args)

    {

        Integer arr[] = new Integer[] { 1, 23, 12, 9,

                                        30, 2, 50 };

        int k = 3;

        kLargest(arr, k);

    }

}
// Этот код предоставлен Камалем Равалом

питон

'' 'Код Python3 для k самых больших элементов в массиве' ''

  

def kLargest(arr, k):

    # Сортировать указанный массив в обратном порядке

    # заказ.

    arr.sort(reverse = True)

    # Распечатать первые k-ые по величине элементы

    for i in range(k):

        print (arr[i], end =" "

  
# Драйверная программа

arr = [1, 23, 12, 9, 30, 2, 50]

# n = len (обр.)

k = 3

kLargest(arr, k)

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

C #

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

using System;

  

class GFG {

    public static void kLargest(int[] arr, int k)

    {

        // Сортировка указанного массива arr в обратном порядке

        // Этот метод не работает с примитивными данными

        // типы. Итак, вместо int, целочисленный тип

        // массив будет использоваться

        Array.Sort(arr);

        Array.Reverse(arr);

  

        // Распечатать первый k-й по величине элемент

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

            Console.Write(arr[i] + " ");

    }

  

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

    public static void Main(String[] args)

    {

        int[] arr = new int[] { 1, 23, 12, 9,

                                30, 2, 50 };

        int k = 3;

        kLargest(arr, k);

    }

}

  
// Этот код предоставлен Rajput-Ji

PHP

<?php 
// PHP-код для k крупнейших
// элементы в массиве

  

function kLargest(&$arr, $n, $k)

{

    // Сортировка заданного массива обр

    // в обратном порядке.

    rsort($arr);

  

    // Распечатать первый kth

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

    for ($i = 0; $i < $k; $i++)

        echo $arr[$i] . " ";

}

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

$arr = array(1, 23, 12, 9, 

                30, 2, 50);

$n = sizeof($arr);

$k = 3;

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

  
// Этот код добавлен
// ChitraNayal
?>

Выход:

50 30 23 

Сложность времени: O (nlogn)

Метод 4 (Использовать Max Heap)
1) Постройте дерево Max Heap в O (n)
2) Используйте Extract Max k раз, чтобы получить k максимум элементов из Max Heap O (klogn)

Временная сложность: O (n + клогн)

Метод 5 (Использовать статистику Одера)
1) Используйте алгоритм статистики заказов, чтобы найти k-й по величине элемент. Пожалуйста, смотрите выбор темы в наихудшем линейном времени O (n)
2) Используйте алгоритм QuickSort Partition для разбиения вокруг k-го наибольшего числа O (n).
3) Сортировка элементов k-1 (элементов больше, чем k-го наибольшего элемента) O (kLogk). Этот шаг необходим, только если требуется отсортированный вывод.

Сложность по времени: O (n), если нам не нужен отсортированный вывод, иначе O (n + kLogk)

Спасибо Шилпи за предложение первых двух подходов.

Метод 6 (использовать Min Heap)
Этот метод в основном является оптимизацией метода 1. Вместо массива temp [] используйте Min Heap.

1) Создайте MH Min 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 наибольших элементов, а корень MH — это k-й по величине элемент.

Сложность времени: O (k + (nk) Logk) без отсортированного вывода. Если требуется отсортированный вывод, то O (k + (nk) Logk + kLogk)

Все вышеперечисленные методы также можно использовать для нахождения k-го наибольшего (или наименьшего) элемента.

C ++

#include <iostream>

using namespace std;

  
// Поменять местами функцию для обмена
// значение переменных x и y

int swap(int& x, int& y)

{

    int temp = x;

    x = y;

    y = temp;

}

  
// Min Heap Class
// arr содержит ссылку на целое число
// размер массива указывает количество
// элементы в Min Heap

class MinHeap {

  

    int size;

    int* arr;

  

public:

    // Конструктор для инициализации размера и обр

    MinHeap(int size, int input[]);

  

    // Min Heapify функция, которая предполагает, что

    // 2 * i + 1 и 2 * i + 2 - минимальная куча и исправляем

    // свойство кучи для i.

    void heapify(int i);

  

    // Создаем минимальную кучу, вызывая heapify

    // для всех неконечных узлов.

    void buildHeap();

};

  
// Конструктор для инициализации данных
// члены и создание средней кучи

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

{

    // Инициализация arr и size

  

    this->size = size;

    this->arr = input;

  

    // Строим Min Heap

    buildHeap();

}

  
// Min Heapify функция, которая предполагает
// 2 * i + 1 и 2 * i + 2 - минимальная куча и
// исправить свойство min heap для i

  

void MinHeap::heapify(int i)

{

    // Если листовой узел, просто вернуть

    if (i >= size / 2)

        return;

  

    // переменная для хранения наименьшего элемента

    // индекс из i, 2 * i + 1 и 2 * i + 2

    int smallest;

  

    // Индекс левого узла

    int left = 2 * i + 1;

  

    // Индекс правого узла

    int right = 2 * i + 2;

  

    // Выбираем минимум с левого узла и

    // текущий узел i и сохранение минимума

    // индекс в наименьшей переменной

    smallest = arr[left] < arr[i] ? left : i;

  

    // Если существует правильный ребенок, сравните и

    // обновляем самую маленькую переменную

    if (right < size)

        smallest = arr[right] < arr[smallest]

                             ? right : smallest;

  

    // Если узел нарушает мин-кучу

    // свойство, поменяйте местами текущий узел i

    // самое маленькое, чтобы исправить свойство min-heap

    // и рекурсивно вызываем heapify для наименьшего узла.

    if (smallest != i) {

        swap(arr[i], arr[smallest]);

        heapify(smallest);

    }

}

  
// Сборка Min Heap

void MinHeap::buildHeap()

{

    // Вызов Heapify для всех неконечных узлов

    for (int i = size / 2 - 1; i >= 0; i--) {

        heapify(i);

    }

}

  

void FirstKelements(int arr[],int size,int k){

    // Создание Min Heap для данного

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

    MinHeap* m = new MinHeap(k, arr);

  

    // цикл для каждого элемента в массиве

    // после k-го элемента

    for (int i = k; i < size; i++) {

  

        // если текущий элемент меньше

        // чем минимальный элемент, ничего не делать

        // и переход к следующему элементу

        if (arr[0] > arr[i])

            continue;

  

        // Иначе изменить минимальный элемент на

        // текущий элемент и вызов heapify для

        // восстановить свойство кучи

        else {

            arr[0] = arr[i];

            m->heapify(0);

        }

    }

    // Теперь min heap содержит максимум k

    // элементы, итерация и печать

    for (int i = 0; i < k; i++) {

        cout << arr[i] << " ";

    }

}
// Программа для водителя

int main()

{

  

    int arr[] = { 11, 3, 2, 1, 15, 5, 4,

                           45, 88, 96, 50, 45 };

  

    int size = sizeof(arr) / sizeof(arr[0]);

  

    // Размер Min Heap

    int k = 3;

  

    FirstKelements(arr,size,k);

  

    return 0;

}
// Этот код предоставлен Ankur Goel

Выход:

50 88 96

Пожалуйста, пишите комментарии, если вы обнаружите, что какое-либо из приведенных выше объяснений / алгоритмов неверно, или найдете более эффективные способы решения той же проблемы.

Ссылки:
http://en.wikipedia.org/wiki/Selection_algorithm

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

k самых больших (или самых маленьких) элементов в массиве | добавлен метод Min Heap

0.00 (0%) 0 votes