1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
|
// 703. Kth Largest Element in a Stream
#include <limits.h>
#include <stdlib.h>
#include <string.h>
/*
* design a class to find the k'th largest element in a stream. note that it is
* the k'th largest element in the sorted order, not the k'th distinct element.
* implement 'KthLargest' class:
* - KthLargest(int k, int[] nums) initialises the objct with the integer 'k'
* and the stream of integers 'nums' int add(int val) appends the integer 'val'
* to the stream and returns the element representing the k'th largest stream
* element
*/
typedef struct {
int *min_heap;
int size;
int curr;
} KthLargest;
int cmp_func(const void *a, const void *b) { return *(int *)a - *(int *)b; }
KthLargest *kthLargestCreate(int k, int *nums, int nums_size) {
if (nums_size)
qsort(nums, nums_size, sizeof(int), cmp_func);
KthLargest *res = malloc(sizeof(KthLargest));
res->size = k;
res->min_heap = malloc(k * sizeof(int));
if (k <= nums_size) {
memcpy(res->min_heap, &nums[nums_size - k], k * sizeof(int));
res->curr = k;
} else {
for (int i = 0; i < k; i++) {
if (i < nums_size)
res->min_heap[i] = nums[i];
else
res->min_heap[i] = INT_MAX;
res->curr = nums_size;
}
}
return res;
}
void swap(int *a, int *b) {
int tmp = *a;
*a = *b;
*b = tmp;
}
int kthLargestAdd(KthLargest *obj, int val) {
if (obj->curr < obj->size) {
obj->min_heap[obj->curr] = val;
int pos = obj->curr;
obj->curr++;
while (pos) {
if (obj->min_heap[pos] < obj->min_heap[(pos - 1) / 2]) {
swap(&obj->min_heap[pos], &obj->min_heap[(pos - 1) / 2]);
pos = (pos - 1) / 2;
} else
break;
}
if (obj->curr == obj->size)
return obj->min_heap[0];
else
return -1;
} else if (obj->curr == obj->size && val > obj->min_heap[0]) {
obj->min_heap[0] = val;
int idx = 0;
while (2 * idx + 1 < obj->size && 2 * idx + 2 < obj->size) {
if (obj->min_heap[2 * idx + 1] <= obj->min_heap[2 * idx + 1]) {
if (obj->min_heap[idx] > obj->min_heap[2 * idx + 1]) {
swap(&obj->min_heap[idx], &obj->min_heap[2 * idx + 1]);
idx = 2 * idx + 1;
} else
break;
} else {
if (obj->min_heap[idx] > obj->min_heap[2 * idx + 2]) {
swap(&obj->min_heap[idx], &obj->min_heap[2 * idx + 2]);
idx = 2 * idx + 2;
} else
break;
}
}
if (2 * idx + 1 < obj->size) {
if (obj->min_heap[idx] > obj->min_heap[2 * idx + 1]) {
swap(&obj->min_heap[idx], &obj->min_heap[2 * idx + 1]);
idx = 2 * idx + 1;
}
}
}
return obj->min_heap[0];
}
void kthLargestFree(KthLargest *obj) {
free(obj->min_heap);
free(obj);
}
int main() {
int k, nums[] = {}, nums_size, val;
KthLargest *obj = kthLargestCreate(k, nums, nums_size);
int param_1 = kthLargestAdd(obj, val);
kthLargestFree(obj);
}
|