Вопрос:

Ссылка: https://practice.geeksforgeeks.org/problems/k-largest-elements4206/1

Имея массив Arr из N положительных целых чисел и целое число K, найдите K самых больших элементов из массива. Элементы вывода должны быть напечатаны в порядке убывания.

Пример 1:

Input:
N = 5, K = 2
Arr[] = {12, 5, 787, 1, 23}
Output: 787 23
Explanation: 1st largest element in the
array is 787 and second largest is 23.

Пример 2:

Input:
N = 7, K = 3
Arr[] = {1, 23, 12, 9, 30, 2, 50}
Output: 50 30 23
Explanation: 3 Largest element in the
array are 50, 30 and 23.

Ваша задача
Вам не нужно ничего читать или печатать. Ваша задача — завершить функцию kLargest(), которая принимает массив целых чисел arr, nиk как параметры и возвращает массив целых чисел, обозначающих ответ. Массив должен быть в порядке убывания.

Ожидаемая временная сложность: O(N + KlogK)
Ожидаемое вспомогательное пространство: O(K+(N-K)*logK)

Ограничения:
1 ≤ K ≤ N ≤ 105
1 ≤ Arr[i] ≤ 106

Решение:

код:

//User function template for C++
class Solution{
public: 
 vector<int> kLargest(int arr[], int n, int k) {
     // code here
     vector<int> ans;
     sort(arr, arr+n, greater<int>());
     for(int i=0; i<k; i++){
         ans.push_back(arr[i]);
     }
     return ans;
 }

};

Подход:

  1. Функция kLargest определена в классе с именем Solution. Это обычная практика в соревновательных соревнованиях по программированию и кодированию.
  2. Внутри функции объявляется вектор с именем ans. Этот вектор будет хранить k самых больших элемента.
  3. Строка sort(arr, arr+n, greater<int>()) используется для сортировки массива arr в порядке убывания с помощью функции sort из стандартной библиотеки C++. greater<int>() — это функция сравнения, определяющая порядок сортировки. Это гарантирует, что элементы отсортированы в порядке убывания.
  4. Затем используется цикл для итерации от индекса 0 до k-1 (включительно). На каждой итерации i-й по величине элемент из отсортированного массива помещается в вектор ans с помощью функции push_back.
  5. Наконец, из функции возвращается вектор ans, содержащий k самых больших элементов.

Временная сложность: O (N log N)

Космическая сложность: O(K)

Заключение:

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