leetcode 703. 数据流中的第K大元素 最小堆解法 c语言

如题：

设计一个找到数据流中第K大元素的类（class）。注意是排序后的第K大元素，不是第K个不同的元素。你的KthLargest类需要一个同时接收整数k 和整数数组nums的构造器，它包含数据流中的初始元素。每次调用KthLargest.add，返回当前数据流中第K大的元素。示例:int k = 3;int[] arr = [4,5,8,2];KthLargest kthLargest = new KthLargest(3, arr);kthLargest.add(3); // returns 4kthLargest.add(5); // returns 5kthLargest.add(10); // returns 5kthLargest.add(9); // returns 8kthLargest.add(4); // returns 8

这道题本意是将一堆数排好序好取第K大的值，刚开始使用二叉搜索树进行排序结果超时。后来改成归并排序，超出时间空间。然后修改成快速排序，还是超时，最后是快排加上冒泡排序，才运行通过，即便如此，耗时超过276ms，看了下c写的最好解法耗时仅48ms，相差N倍。它采用的是最小堆排序，空间复杂度仅需O(k)。

其实像这类海量数据中找前K大的数或者前K小的数，最合适的算法就是堆排序了。堆排序又分为大顶堆和小顶堆。大顶堆指的是节点的子节点都小于它，小顶堆指的是节点的子节点都大于它。这道题显然是使用小顶堆，堆顶即是第K大的数，遍历数组的时候，如果小于堆顶，可以直接丢弃，大于堆顶，则替代堆顶，然后进行堆调整动作。类似的，如果是求第K小的数，那就用大顶堆实现，堆顶即是第K小的数，遇到比堆顶大的数直接丢弃，遇到比堆顶小的数，替代堆顶，然后堆调整。

此外，在使用c语言实现的时候，数组下标记得从1开始，0可以不用，这样写可以避免很多0下标的处理。

堆排序在面试笔试题中相当常见，掌握好的话写出来还是相当快，不懂的同学还是抓紧时间最练习几遍。

下面是本题的C语言最小堆解法代码：

//两个数值互换void swap(int *a, int *b){if (a == b) return;*a = *a ^ *b; *b = *a ^ *b; *a = *a ^ *b;}typedef struct {int maxSize;int heapSize;int *heap;} KthLargest;int kthLargestAdd(KthLargest* obj, int val);//最小堆调整函数，表示调整s的位置。void heapAdjust(int *heap, int s, int e){int i = 1,j;for (j = s << 1; j <= e; j*=2){if (j < e && heap[j] > heap[j+1])j++;if (heap[j] > heap[s])break;swap(heap+j, heap+s);s = j;}return;}//最小堆添加元素void heapInsert(int *heap, int e, int val){int f = 0, i;heap[e] = val;//和父节点比较f = e >> 1;while (f){if (val < heap[f]){swap(heap+e, heap+f);e = f; f = e >> 1; }elsebreak;}return;}KthLargest* kthLargestCreate(int k, int* nums, int numsSize) {int i = 0, j = 0;KthLargest* n = (KthLargest*)calloc(1, sizeof(KthLargest));n->maxSize = k;n->heapSize = 0;n->heap = (int *)calloc((k+1), sizeof(int));for (; i < numsSize; i++)kthLargestAdd(n, nums[i]);return n;}int kthLargestAdd(KthLargest* obj, int val) {int i = 0;//超出堆大小则和堆顶比较，否则插入堆尾，然后自底向上找到合适位置if (obj->heapSize < obj->maxSize){obj->heapSize++;heapInsert(obj->heap, obj->heapSize, val);}else{if(obj->heap[1] < val){obj->heap[1] = val;heapAdjust(obj->heap, 1, obj->heapSize);}}return obj->heap[1];}void kthLargestFree(KthLargest* obj) {free(obj);return;}

=============================================================================================

Linux应用程序、内核、驱动开发交流讨论群(745510310)，感兴趣的同学可以加群讨论、交流、资料查找等，前进的道路上，你不是一个人奥^_^。