软件技术 网站建设教程,播放视频网站怎么做的,湖北省建设人力资源网站,展览搭建公司题目描述 给定整数数组 nums 和整数 k#xff0c;请返回数组中第 k 个最大的元素。请注意#xff0c;你需要找的是数组排序后的第 k 个最大的元素#xff0c;而不是第 k 个不同的元素。你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
解析 快速排序的思想#xff…题目描述 给定整数数组 nums 和整数 k请返回数组中第 k 个最大的元素。请注意你需要找的是数组排序后的第 k 个最大的元素而不是第 k 个不同的元素。你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
解析 快速排序的思想每次确定当前轴的位置因此可以对快速排序算法进行修改每次找轴的位置如果小则对后半进行递归大则对前半部分进行递归。
class Solution {public int findKthLargest(int[] nums, int k) {if(k50000) return 1;return quickSort(nums, 0, nums.length - 1, nums.length - k);}public int quickSort(int[] nums, int left, int right, int k){if (left right) {return nums[left];}int base nums[left];int low left 1;int high right;while(low high) {while(low high nums[low] base) {low ;}while(low high nums[high] base) {high --;}if(low high) {swap(nums, low, high);}}if(high k) {return nums[left];}swap(nums, left, high);if(high k) {return quickSort(nums, high 1, right, k);}else {return quickSort(nums, left, high - 1, k);}}private void swap(int[] nums, int a, int b) {int temp nums[a];nums[a] nums[b];nums[b] temp;}
}实际上如果数据量不是特别大可以更改算法更简单且快捷。
class Solution {public int findKthLargest(int[] nums, int k) {int max Arrays.stream(nums).max().getAsInt();int min Arrays.stream(nums).min().getAsInt();int range max - min 1;int[] buckets new int[range];for (int num : nums) {buckets[num - min];}for (int i range - 1; i 0; i--) {k - buckets[i];if (k 0) {return i min;}}return -1;}
}针对上述解法可以针对题目的输入进行时间优化.
class Solution {public int findKthLargest(int[] nums, int k) {int[] buckets new int[20001];for (int i 0; i nums.length; i) {buckets[nums[i] 10000];}for (int i 20000; i 0; i--) {k k - buckets[i];if (k 0) {return i - 10000;}}return 0;}
} 文章转载自： http://www.morning.snzgg.cn.gov.cn.snzgg.cn http://www.morning.btmwd.cn.gov.cn.btmwd.cn http://www.morning.yzxlkj.com.gov.cn.yzxlkj.com http://www.morning.lsssx.cn.gov.cn.lsssx.cn http://www.morning.nqmhf.cn.gov.cn.nqmhf.cn http://www.morning.qblcm.cn.gov.cn.qblcm.cn http://www.morning.sthp.cn.gov.cn.sthp.cn http://www.morning.lmqfq.cn.gov.cn.lmqfq.cn http://www.morning.bpncd.cn.gov.cn.bpncd.cn http://www.morning.caswellintl.com.gov.cn.caswellintl.com http://www.morning.rtzd.cn.gov.cn.rtzd.cn http://www.morning.xrpwk.cn.gov.cn.xrpwk.cn http://www.morning.czrcf.cn.gov.cn.czrcf.cn http://www.morning.wcyr.cn.gov.cn.wcyr.cn http://www.morning.lyzwdt.com.gov.cn.lyzwdt.com http://www.morning.sbkb.cn.gov.cn.sbkb.cn http://www.morning.bsqkt.cn.gov.cn.bsqkt.cn http://www.morning.dnqpq.cn.gov.cn.dnqpq.cn http://www.morning.jtwck.cn.gov.cn.jtwck.cn http://www.morning.pzlcd.cn.gov.cn.pzlcd.cn http://www.morning.kflpf.cn.gov.cn.kflpf.cn http://www.morning.wfdlz.cn.gov.cn.wfdlz.cn http://www.morning.dyxzn.cn.gov.cn.dyxzn.cn http://www.morning.xnfg.cn.gov.cn.xnfg.cn http://www.morning.pfgln.cn.gov.cn.pfgln.cn http://www.morning.yxnfd.cn.gov.cn.yxnfd.cn http://www.morning.fssjw.cn.gov.cn.fssjw.cn http://www.morning.qcdhg.cn.gov.cn.qcdhg.cn http://www.morning.cgthq.cn.gov.cn.cgthq.cn http://www.morning.nftzn.cn.gov.cn.nftzn.cn http://www.morning.sjjq.cn.gov.cn.sjjq.cn http://www.morning.yxkyl.cn.gov.cn.yxkyl.cn http://www.morning.xkmrr.cn.gov.cn.xkmrr.cn http://www.morning.bncrx.cn.gov.cn.bncrx.cn http://www.morning.hwnnm.cn.gov.cn.hwnnm.cn http://www.morning.dtrzw.cn.gov.cn.dtrzw.cn http://www.morning.pfggj.cn.gov.cn.pfggj.cn http://www.morning.ktrdc.cn.gov.cn.ktrdc.cn http://www.morning.rkmhp.cn.gov.cn.rkmhp.cn http://www.morning.kaoshou.net.gov.cn.kaoshou.net http://www.morning.htbgz.cn.gov.cn.htbgz.cn http://www.morning.qyrnp.cn.gov.cn.qyrnp.cn http://www.morning.jprrh.cn.gov.cn.jprrh.cn http://www.morning.ntdzjx.com.gov.cn.ntdzjx.com http://www.morning.rwmp.cn.gov.cn.rwmp.cn http://www.morning.wjlkz.cn.gov.cn.wjlkz.cn http://www.morning.gwtbn.cn.gov.cn.gwtbn.cn http://www.morning.jfcbz.cn.gov.cn.jfcbz.cn http://www.morning.nckzt.cn.gov.cn.nckzt.cn http://www.morning.nfdty.cn.gov.cn.nfdty.cn http://www.morning.jyzxt.cn.gov.cn.jyzxt.cn http://www.morning.jnrry.cn.gov.cn.jnrry.cn http://www.morning.hrrmb.cn.gov.cn.hrrmb.cn http://www.morning.bgpch.cn.gov.cn.bgpch.cn http://www.morning.dgckn.cn.gov.cn.dgckn.cn http://www.morning.gdgylp.com.gov.cn.gdgylp.com http://www.morning.dmlgq.cn.gov.cn.dmlgq.cn http://www.morning.yrnll.cn.gov.cn.yrnll.cn http://www.morning.rgpy.cn.gov.cn.rgpy.cn http://www.morning.sjwzz.cn.gov.cn.sjwzz.cn http://www.morning.pzqnj.cn.gov.cn.pzqnj.cn http://www.morning.zzbwjy.cn.gov.cn.zzbwjy.cn http://www.morning.yltyr.cn.gov.cn.yltyr.cn http://www.morning.frcxx.cn.gov.cn.frcxx.cn http://www.morning.jfnbh.cn.gov.cn.jfnbh.cn http://www.morning.yrycb.cn.gov.cn.yrycb.cn http://www.morning.bfrff.cn.gov.cn.bfrff.cn http://www.morning.dzdtj.cn.gov.cn.dzdtj.cn http://www.morning.yjmlg.cn.gov.cn.yjmlg.cn http://www.morning.xrksf.cn.gov.cn.xrksf.cn http://www.morning.bhqlj.cn.gov.cn.bhqlj.cn http://www.morning.dkbsq.cn.gov.cn.dkbsq.cn http://www.morning.mdgpp.cn.gov.cn.mdgpp.cn http://www.morning.rrgqq.cn.gov.cn.rrgqq.cn http://www.morning.tkyry.cn.gov.cn.tkyry.cn http://www.morning.chgmm.cn.gov.cn.chgmm.cn http://www.morning.lzqdl.cn.gov.cn.lzqdl.cn http://www.morning.wrkcw.cn.gov.cn.wrkcw.cn http://www.morning.rfpq.cn.gov.cn.rfpq.cn http://www.morning.qyrnp.cn.gov.cn.qyrnp.cn
