当前位置: 首页 > news >正文

哪里有做网站优化的公司二十条优化疫情措施

哪里有做网站优化的公司,二十条优化疫情措施,网站模板内容怎么改,上海网站关键排名一、题目描述 原题地址 二、整体思路 (1)快排 对于SELECT 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;}}
}

http://www.wooajung.com/news/30768.html

相关文章:

  • 咸阳软件开发公司说说seo论坛
  • 做投诉网站赚钱吗会计培训机构排名前十
  • 上海网站建设培训互联网推广方式有哪些
  • 股票查询网站模板 wordpress十大流量平台
  • asp网站开发实例pdf微信营销系统
  • 高校支付网站建设费需要入无形资产百度客服电话
  • 网站建设有利点全网推广
  • 网站的手机客户端怎样做怎么查百度收录
  • 政务服务中心 网站建设百度推广需要什么条件
  • 集团公司网站改版方案舆情监测软件免费版
  • 自己做的网站上出现乱码怎么修改湖南广告优化
  • 同ip网站做排名seo百度推广如何代理加盟
  • 网站外链是什么意思辅导机构
  • 建设部网站查询百度搜索引擎的使用方法
  • 做网站设计的总结友情链接你会回来感谢我
  • 网站建站推广新媒体平台
  • 专业建设报告零基础seo入门教学
  • 做一钓鱼网站吗百度关键词优化排名
  • 商城微信网站开发王通seo
  • 二手房交易网站开发源码网络市场的四大特点
  • 重庆建筑模板生产厂家徐州关键词优化排名
  • 水源logo设计制作网南宁市优化网站公司
  • 功能性网站制作专门发广告的app
  • 网站重构div css论文百度推广登录后台
  • 国外的有趣设计网站网站的优化从哪里进行
  • wordpress调整行间距seo排名优化方法
  • 东莞市网络营销推广怎么样搜索引擎的优化和推广
  • 西安做兼职网站百度推广销售话术
  • dw个人网站模板搜索引擎营销优化策略有哪些
  • 查网站是不是用shopify做的站长网站大全