赞
踩
描述:
给定一个整数数组,让你从该数组中找出最小的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));
- }
-
- }

结果:
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。