首页 > 代码库 > 普林斯顿公开课 算法3-2:求第k大的数
普林斯顿公开课 算法3-2:求第k大的数
问题
给定N个元素的数组,求第k大的数。
特例
当k=0时,就是求最大值,当k=N-1时,就是求最小值。
应用
顺序统计
求top N排行榜
基本思想
使用快速排序方法中的分区思想,使得a[k]左侧没有更小的数,右侧没有更大的数
性能
快速选择算法的复杂度是N。
最坏情况下的复杂度是1/2N^2,但是可以通过预先洗牌来防止出现最坏情况
代码
public class QuickSort { // 对区间 [start, end) 进行分区 public static int partition(Comparable[] a, int start, int end) { // 取出第一个元素作为分区依据 Comparable mid = a[start]; // 每次循环都会交换一次数据 int i = start; int j = end; while(true) { while(true) { i++; if(i >= end) break; if(!SortUtil.less(a[i], mid)) break; } while(true) { j--; if(j < start) break; if(!SortUtil.less(mid, a[j])) break; } if(i >= j) break; SortUtil.exch(a, i, j); } // 将分区依据交换到中间 SortUtil.exch(a, start, j); // 注意:这行容易遗漏 // 返回分区的界线 return j; } //求第k小的数 public static Comparable select(Comparable[] a, int k) { Shuffle.shuffle(a); int lo = 0; int hi = a.length; while(lo < hi) { int mid = partition(a, lo, hi); if(k < mid) { // 注意,这里是k < mid而不是k > mid hi = mid; } else if(k > mid) { lo = mid+1; } else { return a[k]; } } return a[lo]; } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。