面试必考精华版Leetcode215. 数组中的第K个最大元素

题目：

---

代码（2023年10月27日首刷看解析）：

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        return quickselect(nums,k);
    }
 
    int quickselect(vector<int>& nums,int k){
        vector<int> big,equel,small;
        int pivot = nums[rand()%nums.size()];
        for(auto num:nums){
            if(num>pivot){
                big.push_back(num);
            }else if(num
                small.push_back(num);
            }else{
                equel.push_back(num);
            }
        }
        if(k<=big.size()){
            return quickselect(big,k);
        }
        else if(nums.size()-small.size()
            return quickselect(small,k-(nums.size()-small.size()));
        }
        return pivot;
    }
};

        时间复杂度为O(N）

---

代码（二刷自解 超时 2024年3月9日）

struct MyListNode{
    int val;
    MyListNode* prev;
    MyListNode* next;
    MyListNode(int a) : val(a), prev(nullptr), next(nullptr) {}
};
class myQueue{
private:
    MyListNode* dummyHead = new MyListNode(INT_MIN);
    const int n;
    int count = 0;
    void push(int val, MyListNode* node) {
        MyListNode* newnode = new MyListNode(val);
        newnode->prev = node->prev;
        newnode->next = node;
        node->prev->next = newnode;
        node->prev = newnode;
    }
public:
    myQueue(int maxnum) : n (maxnum){
        dummyHead->next = dummyHead;
        dummyHead->prev = dummyHead;
    }
    void insert(int val) {
        MyListNode* cur = dummyHead->next;
        while (val < cur->val) {
            cur = cur->next;
        }
        push(val, cur);
        count++;
        if (count > n) {
            cur = dummyHead->prev;
            cur->prev->next = cur->next;
            cur->next->prev = cur->prev;
            cur->prev = nullptr;
            cur->next =nullptr;
            delete cur;
        }
    }
    int showLast() {
        return dummyHead->prev->val;
    }
};
 
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        myQueue q(k);
        for (int i = 0; i < nums.size(); ++i) {
            q.insert(nums[i]);
        }
        return q.showLast();
    }
};

---

代码（二刷看解析 构建大根堆 2024年3月9日）

class Solution {
public:
    void  maxHeapify(vector<int>& nums, int i, int heapSize) {
        int left = i * 2 + 1;
        int right = i * 2 + 2;
        int largest = i;
 
        if (left < heapSize && nums[left] > nums[largest]) {
            largest = left;
        }
        if (right < heapSize && nums[right] > nums[largest]) {
            largest = right;
        }
 
        if (largest != i) {
            swap(nums[largest], nums[i]);
            maxHeapify(nums, largest, heapSize);
        }
    }
    void buildmaxHeap(vector<int>& nums) {
        int heapSize = nums.size();
        for (int i = heapSize / 2 - 1; i >= 0; --i) {
            maxHeapify(nums, i, heapSize);
        }
    }
    int findKthLargest(vector<int>& nums, int k) {
        buildmaxHeap(nums);//大根堆排序
        int heapSize = nums.size();
        //每次将最大的数和队尾的数互换，并将heapSize-1
        for (int i = 0; i < k - 1; ++i) {
            swap(nums[0], nums[heapSize - 1]);
            --heapSize;
            maxHeapify(nums, 0, heapSize);
        }
        return nums[0];
    }
};