Sponsored
Sponsored
Using a min-heap of size k can efficiently keep track of the kth largest element. This approach relies on the property of a heap where the smallest element (the root) in a min-heap can be accessed in constant time.
Steps:
Time Complexity: O(n log k) for initialization and O(log k) per add operation.
Space Complexity: O(k) for the heap.
1#include <stdlib.h>
2
3typedef struct {
4 int k;
5 int* heap;
6 int heapSize;
7} KthLargest;
8
9int compare(const void* a, const void* b) {
10 return (*(int*)a - *(int*)b);
11}
12
13KthLargest* kthLargestCreate(int k, int* nums, int numsSize) {
14 KthLargest* obj = (KthLargest*)malloc(sizeof(KthLargest));
15 obj->k = k;
16 obj->heap = (int*)malloc(sizeof(int) * k);
17 obj->heapSize = 0;
18 for (int i = 0; i < numsSize; ++i) {
19 kthLargestAdd(obj, nums[i]);
20 }
21 return obj;
22}
23
24int kthLargestAdd(KthLargest* obj, int val) {
25 if (obj->heapSize < obj->k) {
26 obj->heap[obj->heapSize++] = val;
27 qsort(obj->heap, obj->heapSize, sizeof(int), compare);
28 } else if (val > obj->heap[0]) {
29 obj->heap[0] = val;
30 qsort(obj->heap, obj->k, sizeof(int), compare);
31 }
32 return obj->heap[0];
33}
34
35void kthLargestFree(KthLargest* obj) {
36 free(obj->heap);
37 free(obj);
38}This C approach doesn't directly use a native heap library but replicates a heap's behavior. It uses an array and sorts it, mimicking the min-heap functionality, maintaining the top k largest values.