[Leetcode 215][Medium]-数组中的第K个最大元素-快排/小根堆/堆排序

一、题目描述

原题地址

二、整体思路

（1）快排

                对于SELECT K问题，可以通过三路快排解决，快排可以把一个元素放至按升序排序的数组正确的位置，左边为小于该元素的元素集合，右边为大于该元素的元素集合。

三路快排把数组分成三部分：

 [l,l2-1]：<nums[l]的元素区间；[l2,r2-1]:=nums[l]的元素区间；[r2,r]：>nums[l]的元素区间；

当k位于[l2,r2-1]区间时，说明数组中[l2,r2-1]区间的元素都放置到正确的位置，k在其中说明k所指的元素已经排序至正确位置，可以返回。

当k位于[l,l2-1]区间时，说明还需要对[l,l2-1]进行快速排序，同理当k位于[r2,r]区间时，说明要对[r2,r]进行快速排序。

（2）小根堆

                要选择第K个最大元素，则可以把该数组[0,k-1]的部分转化为小根堆，遍历[k,nums.length-1]的部分，若遍历到的元素大于堆顶元素，则可以交换此两元素，然后对新的堆顶元素进行siftDown下沉操作，重复上述步骤，最终可以得到前K个最大元素组成的小根堆，堆顶即为第K大的元素。

（3）原地堆排序、大根堆

                对整个数组进行堆排序形成大根堆。把堆顶元素与数组末尾元素进行交换，这样可以得到第一大的元素。把新的堆顶元素在[0,nums.length-1)处进行siftdown()下沉操作，此时的堆顶元素即为数组第二大的元素，那么又可以与数组的[nums.length-2]元素进行交换得到新的堆。重复上述步骤直到得到数组第K大的元素。

三、代码

//快排
class Solution {public int findKthLargest(int[] nums, int k) {Random random=new Random();quicksort(nums,0,nums.length-1,nums.length-k,random);return nums[nums.length-k];}public void quicksort(int[] nums,int l,int r,int k2,Random random){if(l>=r) return;//把nums[l]与数组中随机位置的元素进行交换//防止快排退化导致时间复杂度增加int p=random.nextInt(r-l+1)+l;int temp3=nums[l];nums[l]=nums[p];nums[p]=temp3;int i=l+1,l2=l,r2=r+1;while(i<r2){
//[l,l2]:<nums[l]元素区间;[l2+1,i-1]:=nums[l]元素区间;[r2,r]:>nums[l]//元素区间if(nums[i]<nums[l]){int temp=nums[++l2];nums[l2]=nums[i];nums[i]=temp;i++;}else if(nums[i]>nums[l]){int temp4=nums[--r2];nums[r2]=nums[i];nums[i]=temp4;}else{i++;}}
//最后把nums[l]与nums[l2]交换int temp2=nums[l];nums[l]=nums[l2];nums[l2]=temp2;
//区间发生变化。[l,l2-1]:<;[l2,r2-1]:=;[r2,r]:>if(k2>=l2 && k2<=r2-1) return;else if(r2<=k2) quicksort(nums,r2,r,k2,random);else quicksort(nums,l,l2-1,k2,random);}
}

//小根堆
class Solution {public int findKthLargest(int[] nums, int k) {//把数组[0,k-1]的部分化为小根堆for(int i=(k-2)/2;i>=0;i--){siftDown(nums,i,k);}//遍历数组剩下部分，同时把小根堆堆顶替换为更大的数组元素并对新堆顶执行下沉操作for(int i=k;i<nums.length;i++){if(nums[i]>nums[0]){int temp=nums[i];nums[i]=nums[0];nums[0]=temp;siftDown(nums,0,k);}}return nums[0];//此时小根堆代表前K大的元素，堆顶表示第K大的元素}public void siftDown(int[] arr,int i,int n){while((i*2+1)<n){int j=i*2+1;if(j+1<n && arr[j+1]<arr[j]) j++;if(arr[i]>arr[j]){int temp2=arr[i];arr[i]=arr[j];arr[j]=temp2;i=j;}else break;}}
}

//堆排序，大根堆
class Solution {public int findKthLargest(int[] nums, int k) {\//把整个数组化为大根堆for(int i=(nums.length-2)/2;i>=0;i--){siftDown(nums,i,nums.length);}int ret=0;//从数组末尾由后到前遍历，交换堆顶元素，把元素从最大元素到最小元素的顺序排序for(int i=nums.length-1,k2=0;i>=0;i--){swap(nums,0,i);siftDown(nums,0,i);k2++;if(k2==k) return nums[i];}return ret;}public void swap(int[] nums,int i,int j){int temp=nums[i];nums[i]=nums[j];nums[j]=temp;}public void siftDown(int[] nums,int i,int n){while((i*2+1)<n){//存在左子结点时int j=i*2+1;if(j+1<n && nums[j+1]>nums[j]) j++;//存在右子节点且右子节点比左子节点更大时if(nums[i]<nums[j]){//较小的儿子节点比当前节点大时，要下沉当前节点swap(nums,i,j);i=j;}else break;}}
}