TopK问题 |
您所在的位置：网站首页 › 龙膜怎么区分真假 › TopK问题 |
|
Leetcode中有这样一道题215. 数组中的第K个最大元素，也是面试中的常考题，我做一个记录。 通常解法这道题通常的解法有两种，一个是堆排序，一个是快速选择，都需要掌握。 1.快速选择 class Solution { public int findKthLargest(int[] nums, int k) { //快速选择方法 从小到大排列 目标是找 第n-k位置的元素 return help(nums,0,nums.length-1,nums.length-k); } public int help(int[]nums, int left, int right, int k){ int idx = partition(nums,left,right); if(idxk) return help(nums,left,idx-1,k); return nums[idx]; } public int partition(int[]nums, int left,int right){ int pivot = nums[left]; int i=left,j=right; while(i if(left public int findKthLargest(int[] nums, int k) { PriorityQueue q = new PriorityQueue((a,b)->(a-b)); for(int num:nums){ if(q.size()q.peek()){ q.offer(num); } if(q.size()>k){ q.poll(); } } return q.peek(); } }还可以手动建堆 海量数据如果是海量数据，数据很多并不能全部读入内存进行排序，又应该怎么办呢？ 假设有1亿个浮点数，找出其中最大的10000个。 可以使用分治的方法，先将1亿个数据分成100份，1份有100万个数据。使用之前提到的快速选择或者最小堆问题选出每一堆的前10000个数据，再将这100个10000数据做一次选择。 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |