首页 > 代码库 > 找出一堆数中最小的前K个数
找出一堆数中最小的前K个数
描写叙述:
给定一个整数数组。让你从该数组中找出最小的K个数
思路:
最简洁粗暴的方法就是将该数组进行排序,然后取最前面的K个数就可以。
可是,本题要求的仅仅是求出最小的k个数就可以,用排序能够但显然有点浪费。比方让求10000个整数数组中的最小的10个数。用排序的话平均时间复杂度差为Nlog(N)。
于是想到了,用堆来实现,可是自己实现又太麻烦。想到了java里面的TreeSet,先将K个数放入TreeSet中。因为TreeSet会对里面的元素进行排序。所以在TreeSet中的元素是有序的。以后没插入一个元素,将TreeSet中的最大元素删除就可以,所以TreeSet动态维持K个元素且这K个元素是有序的。
代码:
import java.util.TreeSet; public class FirstKElements { public static TreeSet<Integer>getFirstKElements(int arr[],int k) { TreeSet<Integer>set=new TreeSet<Integer>(); int len=arr.length; k=k%len; int i=0; int num=0; for(i=0;i<k;i++) set.add(arr[i]); for(i=k;i<len;i++) { set.add(arr[i]); num=set.last(); set.remove(num); } return set; } public static void main(String[] args) { // TODO Auto-generated method stub int arr[]={9,7,5,4,2,1,3,6,8}; System.out.println(FirstKElements.getFirstKElements(arr, 4)); } }结果:
找出一堆数中最小的前K个数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。