有关做生态环境的官方网站,seo排名优化培训价格,手机模板网站模板下载网站,网络舆情监测方案一、题目描述
原题地址 二、整体思路
#xff08;1#xff09;快排 对于SELECT K问题#xff0c;可以通过三路快排解决#xff0c;快排可以把一个元素放至按升序排序的数组正确的位置#xff0c;左边为小于该元素的元素集合#xff0c;右边为大于该元素的元素集合。
三…
一、题目描述
原题地址 二、整体思路
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 randomnew 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(lr) return;//把nums[l]与数组中随机位置的元素进行交换//防止快排退化导致时间复杂度增加int prandom.nextInt(r-l1)l;int temp3nums[l];nums[l]nums[p];nums[p]temp3;int il1,l2l,r2r1;while(ir2){
//[l,l2]:nums[l]元素区间;[l21,i-1]:nums[l]元素区间;[r2,r]:nums[l]//元素区间if(nums[i]nums[l]){int tempnums[l2];nums[l2]nums[i];nums[i]temp;i;}else if(nums[i]nums[l]){int temp4nums[--r2];nums[r2]nums[i];nums[i]temp4;}else{i;}}
//最后把nums[l]与nums[l2]交换int temp2nums[l];nums[l]nums[l2];nums[l2]temp2;
//区间发生变化。[l,l2-1]:;[l2,r2-1]:;[r2,r]:if(k2l2 k2r2-1) return;else if(r2k2) 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;i0;i--){siftDown(nums,i,k);}//遍历数组剩下部分同时把小根堆堆顶替换为更大的数组元素并对新堆顶执行下沉操作for(int ik;inums.length;i){if(nums[i]nums[0]){int tempnums[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*21)n){int ji*21;if(j1n arr[j1]arr[j]) j;if(arr[i]arr[j]){int temp2arr[i];arr[i]arr[j];arr[j]temp2;ij;}else break;}}
}
//堆排序大根堆
class Solution {public int findKthLargest(int[] nums, int k) {\//把整个数组化为大根堆for(int i(nums.length-2)/2;i0;i--){siftDown(nums,i,nums.length);}int ret0;//从数组末尾由后到前遍历交换堆顶元素把元素从最大元素到最小元素的顺序排序for(int inums.length-1,k20;i0;i--){swap(nums,0,i);siftDown(nums,0,i);k2;if(k2k) return nums[i];}return ret;}public void swap(int[] nums,int i,int j){int tempnums[i];nums[i]nums[j];nums[j]temp;}public void siftDown(int[] nums,int i,int n){while((i*21)n){//存在左子结点时int ji*21;if(j1n nums[j1]nums[j]) j;//存在右子节点且右子节点比左子节点更大时if(nums[i]nums[j]){//较小的儿子节点比当前节点大时要下沉当前节点swap(nums,i,j);ij;}else break;}}
}
