当前位置:   article > 正文

找出一堆数中最小的前K个数_找出前k小个数

找出前k小个数

描述:

给定一个整数数组,让你从该数组中找出最小的K个数

思路:

最简洁粗暴的方法就是将该数组进行排序,然后取最前面的K个数即可。但是,本题要求的只是求出最小的k个数即可,用排序可以但显然有点浪费,比如让求10000个整数数组中的最小的10个数,用排序的话平均时间复杂度差为Nlog(N)。

于是想到了,用堆来实现,但是自己实现又太麻烦,想到了java里面的TreeSet,先将K个数放入TreeSet中,由于TreeSet会对里面的元素进行排序,所以在TreeSet中的元素是有序的,以后没插入一个元素,将TreeSet中的最大元素删除即可,所以TreeSet动态维持K个元素且这K个元素是有序的。

代码:

  1. import java.util.TreeSet;
  2. public class FirstKElements
  3. {
  4. public static TreeSet<Integer>getFirstKElements(int arr[],int k)
  5. {
  6. TreeSet<Integer>set=new TreeSet<Integer>();
  7. int len=arr.length;
  8. k=k%len;
  9. int i=0;
  10. int num=0;
  11. for(i=0;i<k;i++)
  12. set.add(arr[i]);
  13. for(i=k;i<len;i++)
  14. {
  15. set.add(arr[i]);
  16. num=set.last();
  17. set.remove(num);
  18. }
  19. return set;
  20. }
  21. public static void main(String[] args)
  22. {
  23. // TODO Auto-generated method stub
  24. int arr[]={9,7,5,4,2,1,3,6,8};
  25. System.out.println(FirstKElements.getFirstKElements(arr, 4));
  26. }
  27. }
结果:


声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/Gausst松鼠会/article/detail/716760
推荐阅读
相关标签
  

闽ICP备14008679号