讨论/《堆》 - 215. 数组中的第 K 个最大元素/
《堆》 - 215. 数组中的第 K 个最大元素
共 3 个回复

Python解法,感谢作者指导

import heapq
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        maxHeap = []
        heapq.heapify(maxHeap)
        for num in nums:
            heapq.heappush(maxHeap,num*-1)
        
        for i in range(k-1):
            heapq.heappop(maxHeap)
        return -heapq.heappop(maxHeap)
// C语言 
typedef struct {
    int *d;
    int len;
} SqList;

void swap(SqList *obj, int a, int b) {
    int t = obj->d[a];
    obj->d[a] = obj->d[b];
    obj->d[b] = t;
}

void HeadAdjust(SqList *obj, int st, int len) {
    int j, tmp;
    tmp = obj->d[st];
    for (j = 2 * st; j <= len; j *= 2) { // j 2倍增长
        if (j < len && obj->d[j] < obj->d[j + 1]) {
            j++;
        }
        if (tmp >= obj->d[j]) {
            break;
        }
        obj->d[st] = obj->d[j];
        st = j;
    }
    obj->d[st] = tmp;
}

void HeapSort(SqList *obj) {
    int i, j;
    for (i = obj->len / 2; i > 0; i--) { // 大于0
        HeadAdjust(obj, i, obj->len);
    }
    for (i = obj->len; i > 1; i--) { // 大于1 
        swap(obj, i, 1);
        HeadAdjust(obj, 1, (i - 1)); // [1, i - 1] 重新·调整
    }
}

int findKthLargest(int* nums, int numsSize, int k){
    SqList obj;
    obj.d = (int *)malloc(sizeof(int) * (numsSize + 1));

    obj.len = numsSize;
    int i;
    for (i = 0; i < numsSize; i++) {
        obj.d[i + 1] = nums[i];
    }
    HeapSort(&obj);

    return obj.d[numsSize - k + 1];
}
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int> q;
        for(auto now : nums){
            q.push(-now);
            if(q.size() == k + 1){
                q.pop();
            }
        }
        return -q.top();
    }
};