Вопрос:
Ссылка: 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; } };
Подход:
- Функция
kLargest
определена в классе с именемSolution
. Это обычная практика в соревновательных соревнованиях по программированию и кодированию. - Внутри функции объявляется вектор с именем
ans
. Этот вектор будет хранитьk
самых больших элемента. - Строка
sort(arr, arr+n, greater<int>())
используется для сортировки массиваarr
в порядке убывания с помощью функцииsort
из стандартной библиотеки C++.greater<int>()
— это функция сравнения, определяющая порядок сортировки. Это гарантирует, что элементы отсортированы в порядке убывания. - Затем используется цикл для итерации от индекса 0 до
k-1
(включительно). На каждой итерацииi
-й по величине элемент из отсортированного массива помещается в векторans
с помощью функцииpush_back
. - Наконец, из функции возвращается вектор
ans
, содержащийk
самых больших элементов.
Временная сложность: O (N log N)
Космическая сложность: O(K)
Заключение:
Надеюсь, что решение окажется полезным и вам, ребята, понравилось. Давайте обсудим новые подходы. Пожалуйста, прокомментируйте, если у вас есть предложения и сомнения, которые необходимо развеять.