数组中的第K个最大元素

题目：

思考1：

1. 使用堆排序实现
2. 堆排序有两种思路：
   1. 使用大根堆，将数组所有元素使用大根堆建堆，使用k-1次堆的删除操作后的堆顶就是索要元素
   2. 使用小根堆，将数组前k个元素建立小根堆，遍历数组中其他元素，若遍历到的元素大于堆顶则删除堆顶并将该遍历到的元素加入堆中（也就是说始终维持一个大小k的小根堆，小根堆里面存储的元素随着遍历过程的进行会不断更新成较大的元素），遍历完成后堆顶就是第k大元素（k-1个更大的元素都在堆里面了）-----比起大根堆法省下一些空间~~

实现采用小根堆方法：

class Solution {
public:void adjust(vector<int>& heap,int t){int max=t;while(2*max+1<heap.size()){int l=2*max+1;int r=2*max+2;if (r<heap.size()){if (heap[l]<heap[r]){if (heap[l]<heap[max]){swap(heap[l],heap[max]);max=l;}else {break;}}else{if (heap[r]<heap[max]){swap(heap[r],heap[max]);max=r;}else{break;}}}else{if (heap[l]<heap[max]){swap(heap[l],heap[max]);max=l;}else {break;}}}}int findKthLargest(vector<int>& nums, int k) {vector<int> heap(nums.begin(),nums.begin()+k);int max=k/2-1;for (int i=max;i>=0;--i){adjust(heap,i);}for (int i=k;i<nums.size();i++){if (nums[i]>heap[0]){heap[0]=nums[i];adjust(heap,0);}}return heap[0];}
};

思考二:

1. 虽说堆排序的思考和实现已经蛮好的了，但仍然未满足要求
2. 对于时间复杂度低的排序，想到快速排序的基于哨兵+划分的思路，由于并不需要完全排序整个数组，可以根据哨兵和k的位置进行快速选择定位，显著降低时间复杂度
3. 注意巨坑（普通划分会有很多重复元素不特殊处理会导致超时的）-----》三路划分

实现：

class Solution {
public:int findKthLargest(vector<int>& nums, int k) {return quickSelect(nums, 0, nums.size() - 1, k);}private:int quickSelect(vector<int>& nums, int left, int right, int k) {if (left == right) return nums[left]; int pivotIndex = left + rand() % (right - left + 1);int pivot = nums[pivotIndex];int i = left, j = right, p = left;while (p <= j) {if (nums[p] > pivot) {swap(nums[p], nums[i]);i++;p++;} else if (nums[p] < pivot) {swap(nums[p], nums[j]);j--;} else {p++;}}int bigCount = i - left;int equalCount = j - i + 1;if (k <= bigCount) {return quickSelect(nums, left, i - 1, k);} else if (k <= bigCount + equalCount) {return pivot; } else {return quickSelect(nums, j + 1, right, k - bigCount - equalCount);}}
};