力扣703题解答c语言

### LeetCode 703 Kth Largest Element in a Stream 的 C语言实现 此问题的核心在于通过维护一个小顶堆来动态跟踪数据流中的前 `k` 大元素。以下是基于题目需求的完整解决方案。 #### 小顶堆的概念 为了高效解决该问题，可以利用最小堆（min heap），它始终保持大小为 `k`。这样，在每次插入新元素时，只需比较当前元素与堆顶元素即可决定是否更新堆的内容[^2]。 #### 实现细节 1. **初始化阶段**：构建初始的小顶堆，确保其容量不超过 `k`。 2. **添加操作**：对于每一个新增加的数据项，判断是否需要替换掉现有的堆顶元素。 3. **返回结果**：调用 `add()` 方法后立即返回堆顶元素作为当前第 `k` 大值。 下面是完整的 C语言版本代码： ```c #include <stdio.h> #include <stdlib.h> typedef struct { int* pq; int size; int capacity; int k; } KthLargest; // 上浮调整函数 void swim(KthLargest* obj, int pos) { while (pos > 0 && obj->pq[(pos - 1)/2] > obj->pq[pos]) { int temp = obj->pq[pos]; obj->pq[pos] = obj->pq[(pos - 1)/2]; obj->pq[(pos - 1)/2] = temp; pos = (pos - 1)/2; } } // 下沉调整函数 void sink(KthLargest* obj, int pos) { while (2 * pos + 1 < obj->size) { int j = 2 * pos + 1; if (j + 1 < obj->size && obj->pq[j + 1] < obj->pq[j]) j++; if (!(obj->pq[pos] > obj->pq[j])) break; int temp = obj->pq[pos]; obj->pq[pos] = obj->pq[j]; obj->pq[j] = temp; pos = j; } } KthLargest* kthLargestCreate(int k, int* nums, int numsSize) { KthLargest* obj = malloc(sizeof(KthLargest)); obj->capacity = k; obj->size = 0; obj->k = k; obj->pq = calloc(k, sizeof(int)); for (int i = 0; i < numsSize; ++i) { if (obj->size < k) { obj->pq[obj->size++] = nums[i]; swim(obj, obj->size - 1); } else if (nums[i] > obj->pq[0]) { obj->pq[0] = nums[i]; sink(obj, 0); } } return obj; } int kthLargestAdd(KthLargest* obj, int val) { if (obj->size < obj->k) { obj->pq[obj->size++] = val; swim(obj, obj->size - 1); } else if (val > obj->pq[0]) { obj->pq[0] = val; sink(obj, 0); } return obj->pq[0]; } void kthLargestFree(KthLargest* obj) { free(obj->pq); free(obj); } ``` 以上代码实现了所需的类及其方法，并提供了内存管理功能以释放分配的空间[^4]。 #### 测试样例验证 假设输入如下： ```plaintext int main(){ int arr[] = {4,5,8,2}; KthLargest* kl = kthLargestCreate(3, arr, 4); printf("%d\n", kthLargestAdd(kl, 3)); // 输出 4 printf("%d\n", kthLargestAdd(kl, 5)); // 输出 5 printf("%d\n", kthLargestAdd(kl, 10)); // 输出 5 printf("%d\n", kthLargestAdd(kl, 9)); // 输出 8 printf("%d\n", kthLargestAdd(kl, 4)); // 输出 8 kthLargestFree(kl); return 0; } ``` 运行上述程序会得到预期的结果序列。