Sponsored
Sponsored
By using a Min-Heap, we can efficiently keep track of the k largest elements. Maintain a heap of size k, and for each element in the array, decide whether to add it to the heap. If you add an element to the heap when it is full, remove the minimum element to maintain the size of the heap as k. At the end, the root of the heap will be the kth largest element.
Time Complexity: O(n log n), where n is the size of the array, because of the sorting operation.
Space Complexity: O(1), as we are modifying the input array in-place.
1#include <stdio.h>
2#include <stdlib.h>
3
4int cmpfunc (const void * a, const void * b) {
5 return (*(int*)a - *(int*)b);
6}
7
8int findKthLargest(int* nums, int numsSize, int k) {
9 qsort(nums, numsSize, sizeof(int), cmpfunc);
10 return nums[numsSize - k];
11}
12
13int main() {
14 int nums[] = {3,2,1,5,6,4};
15 int k = 2;
16 int numsSize = sizeof(nums) / sizeof(nums[0]);
17 printf("%d\n", findKthLargest(nums, numsSize, k));
18 return 0;
19}We first define a comparison function cmpfunc that is used by the C library function qsort to sort the array. After sorting, the kth largest element is located at index numsSize - k.
Quickselect is an efficient selection algorithm to find the kth smallest element in an unordered list. The algorithm is related to the quicksort sorting algorithm. It works by partitioning the data, similar to the partitioning step of quicksort, and is based on the idea of reducing the problem size through partitioning.
Average-case Time Complexity: O(n), but worst-case O(n²).
Space Complexity: O(1) for iterative solution, O(log n) for recursive calls due to stack depth.
1#include <iostream>
2#include <vector>
#include <algorithm>
int partition(std::vector<int>& nums, int left, int right) {
int pivot = nums[right];
int i = left;
for (int j = left; j < right; ++j) {
if (nums[j] > pivot) {
std::swap(nums[i++], nums[j]);
}
}
std::swap(nums[i], nums[right]);
return i;
}
int quickSelect(std::vector<int>& nums, int left, int right, int k) {
if (left < right) {
int pivotIndex = partition(nums, left, right);
if (pivotIndex == k) return nums[pivotIndex];
else if (pivotIndex < k) return quickSelect(nums, pivotIndex + 1, right, k);
else return quickSelect(nums, left, pivotIndex - 1, k);
}
return nums[left]; // if left == right
}
int findKthLargest(std::vector<int>& nums, int k) {
return quickSelect(nums, 0, nums.size() - 1, k - 1);
}
int main() {
std::vector<int> nums = {3,2,1,5,6,4};
int k = 2;
std::cout << findKthLargest(nums, k) << std::endl;
return 0;
}The C++ implementation closely follows the concept of Quickselect, tending to partition results around the pivot. Elements to the left of the pivot are larger if we're looking for a kth largest (thus slightly inversed logical operations). Using recursion, we trim partitions around the region surrounding the desired kth position.