最小的K个数

问题描述

输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。

思路分析(解法一)

可先将整数数组进行排序，利用快排（nlogn）为从小到大，然后取出前k项

码上有戏

public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> list=new ArrayList<Integer>();
        if(k<0||k>input.length)
            return list;      
        Arrays.sort(input);
        for(int i=0;i<k;i++)
            list.add(input[i]);
        return list;
    }

思路分析(解法二)

这里可进行海量数据的处理，先将前k个数据放在treeset中，这里数据不能重复，并且是按照红黑树从小到大存储，然后依次比较k之后的元素，如果小于最大的，就替换掉，最后遍历完成后就是所求的

码上有戏

public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
              ArrayList<Integer> list=new ArrayList<Integer>();
            if(k<=0||k>input.length||input.length==0||input==null)
                return list; 
            TreeSet<Integer> s=new TreeSet<Integer>();
            for(int i=0;i<input.length;i++){
                if(s.size()<k){
                    s.add(input[i]);
                }else{
                    if(input[i]<s.last()){
                        s.remove(s.last());
                        s.add(input[i]);
                    }
                }
            }
            Iterator<Integer> it=s.iterator();
            while(it.hasNext()){
                list.add(it.next());
            }
            return list;
        }