【leetcode】215. 数组中的第K个最大元素

#include <vector>
#include <math.h>
#include <limits.h>

using namespace std;

// 快速选择
// 时间复杂度O(n)
// 空间复杂度O(logn)，递归调用
class Solution1 {
public:
    void quick_find(vector<int>& nums, int k, int left, int right) {
       if (left > right) return;

       int pivot = nums[left];
       int i = left, j = right;

       while (i != j) {
          while (nums[j] > pivot && i < j) {
             --j;
          }
          while (nums[i] <= pivot && i < j) {
             ++i;
          }
          swap(nums[i], nums[j]);
       }

       nums[left] = nums[i];
       nums[i] = pivot;

       if (i > k - 1) {
          quick_find(nums, k, left, i-1);
       } else if (i < k - 1) {
          quick_find(nums, k, i+1, right);
       }
    }

    // 全程需注意第K大的数下标是K-1
    int findKthLargest(vector<int>& nums, int k) {
        int n = nums.size();
        
        // 转化：找第k个最大的数即找第n - k + 1大的数
        k = n - k + 1;
        
        quick_find(nums, k, 0, n-1);
        
        return nums[k - 1];
    }
};

// 二叉堆
// 时间复杂度O(nlogn)，建堆O(n)，移除堆顶O(klogn)
// 空间复杂度O(logn)，递归代价
class Solution {
public:
    // 维护堆的性质
    // heap为需要维护的堆
    // i为需要调整的节点
    // heap_size为堆的大小
    void maxHeapify(vector<int>& heap, int i, int heap_size) {
       int left = 2 * i + 1;
       int right = 2 * i + 2;
       int max = i;

       if (left < heap_size && heap[left] > heap[max]) {
          max = left;
       }
       if (right < heap_size && heap[right] > heap[max]) {
          max = right;
       }
       if (max != i) {
          swap(heap[i], heap[max]);
          maxHeapify(heap, max, heap_size); // 继续调整交换后的节点
       }
       // 隐含停止条件：i为叶子节点
    }

    void buildHeap(vector<int>& nums) {
       // 叶子节点不用调整，因为没有孩子，所以调整也没用
       // 从底到上进行调整
       for (int i = nums.size()/2; i >= 0; --i) {
          maxHeapify(nums, i, nums.size());
       }
    }

    int findKthLargest(vector<int>& nums, int k) {
       buildHeap(nums);

       int n = nums.size();
       int heap_size = nums.size();

       // 倒数第K大需要删除K-1次根节点
       for (int i = 0; i < k - 1; ++i) {
          swap(nums[n - i - 1], nums[0]);
          // 将堆的大小减1，这里只是假的减去
          --heap_size; 
          // 从根进行调整
          maxHeapify(nums, 0, heap_size);
       }

       return nums[0];
    }
};

int main() {
   Solution s;
   int k = 2;
   vector<int> input{ 3,2,1,5,6,4 };
   int result = s.findKthLargest(input, k);
   int a = 0;
}