LeetCode-215.数组中的第K个最大元素

. - 力扣（LeetCode）给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:

输入: [3,2,1,5,6,4], k = 2
输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4

提示：

• 1 <= k <= nums.length <= 105
• -104 <= nums[i] <= 104

思路1：基于堆排序的选择方法

排序 - - - 选择排序（简单选择、堆排序）_c#排序中选择排序中的dui排序-CSDN博客

「调整」

        父节点都大于或小于子结点

// 以root为根，调整大根堆
    void heapAdjust(vector<int>& nums, int root, int heapSize){
        int i = root;  // i保存根节点下标
        for(int j = i*2 + 1; j < heapSize; j = i*2+1){
            // j保存孩子中最大值下标
            if(j < heapSize - 1 && nums[j] < nums[j+1]){
                j++;
            }
            
            if(nums[i] >= nums[j]){
                break;
            }
            else{
                swap(nums[i], nums[j]);
                i = j;
            }
        }
    }

「建堆」

        将排序码k1，k2，k3，…，kn表示成一棵完全二叉树，然后从第 n/2个排序码(即树的最后一个非终端结点)开始筛选，使由该结点作根结点组成的子二叉树符合堆的定义，然后从第 n/2-1 个排序码重复刚才操作，直到第一个排序码止。

void buildHeap(vector<int>&nums, int heapSize){
        for(int i = heapSize / 2; i >= 0; i--){
            heapAdjust(nums, i, heapSize);
        }
    }

「删除」

        将堆中第一个结点（二叉树根结点）和最后一个结点的数据进行交换（k1与kn），再将k1~kn-1重新建堆，然后k1和kn-1交换，再将k1~kn-2重新建堆，然后k1和kn-2交换，如此重复下去，每次重新建堆的元素个数不断减1，直到重新建堆的元素个数仅剩一个为止。这时堆排序已经完成，则排序码k1，k2，k3，…，kn已排成一个有序序列。

class Solution {
private:
    // 以root为根，调整大根堆
    void heapAdjust(vector<int>& nums, int root, int heapSize){
        int i = root;  // i保存根节点下标
        for(int j = i*2 + 1; j < heapSize; j = i*2+1){
            // j保存孩子中最大值下标
            if(j < heapSize - 1 && nums[j] < nums[j+1]){
                j++;
            }
            
            if(nums[i] >= nums[j]){
                break; // 因为从叶子节点向上调节，所以没有节点交换，其子树也不许变化
            }
            else{
                swap(nums[i], nums[j]);
                i = j; // j节点调整，其子树也需要调整
            }
        }
    }
    void buildHeap(vector<int>&nums, int heapSize){
        for(int i = heapSize / 2; i >= 0; i--){
            heapAdjust(nums, i, heapSize);
        }
    }

public:
    int findKthLargest(vector<int>& nums, int k) {
        int heapSize = nums.size();
        buildHeap(nums, heapSize);
        
        // 第k大数倒数
        for(int i = nums.size() - 1; i > nums.size() - k; --i){
            swap(nums[0],nums[i]);
            --heapSize;
            heapAdjust(nums, 0, heapSize);
        }
        return nums[0];

    }
};

思路2：基于快速排序的选择方法

排序 - - - 交换排序（快速排序、冒泡排序）-CSDN博客

class Solution {
private:
    int partition(vector<int>&nums, int l, int r){
        int key = nums[l];
        while(l < r){
            while(l < r && nums[r] >= key) r--;
            nums[l] = nums[r];
            while(l < r && nums[l] <= key) l++;
            nums[r] = nums[l];
        }
        nums[l] = key;
        return l;
    }

    int quickSelect(vector<int>& nums, int l, int r, int k){
        int index = partition(nums, l, r);
        if(index == k)
            return nums[k];
        else
            return index < k 
            ? quickSelect(nums, index + 1, r, k)  // index数小于第k数则在index右边查找
             : quickSelect(nums, l, index - 1, k); // index数大于第k数则在index左边查找
    }

public:
    int findKthLargest(vector<int>& nums, int k) {
        return quickSelect(nums, 0, nums.size() - 1, nums.size() - k); // 返回倒数k位置数
    }
};