首页 > 代码库 > 普林斯顿大学算法课 Algorithm Part I Week 3 求第K大数 Selection
普林斯顿大学算法课 Algorithm Part I Week 3 求第K大数 Selection
问题
给定N个元素的数组，求第k大的数。
特例
当k=0时，就是求最大值，当k=N-1时，就是求最小值。
应用
顺序统计
求top N排行榜
基本思想
使用快速排序方法中的分区思想，使得a[k]左侧没有更小的数，右侧没有更大的数
性能
快速选择算法的复杂度是N。
最坏情况下的复杂度是1/2N^2，但是可以通过预先洗牌来防止出现最坏情况
public static Comparable select(Comparable[] a, int k){ StdRandom.shuffle(a); int lo = 0, hi = a.length - 1; while ( hi > lo) { int j = partition(a, lo, hi); if (j < k) lo = j + 1; else if (j > k) hi = j - 1; else return a[k]; } return a[k];}
原文地址
普林斯顿大学算法课 Algorithm Part I Week 3 求第K大数 Selection
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。