牛客_最小的k个数

题目描述

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

思路：

一、冒泡法的原理

由于是在寻找出n个数字中最小的k个数，可以采用冒泡法的原理，每次冒出一个最小值，将这个最小值添加到辅助输出数组中

或者是先调用Arrays的sort方法直接排序再选择输出。

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> result= new ArrayList<Integer>();
        //当输入数组为空，或者输入数组长度小于k的值返回为null
        if(input.length==0||k<=0||k>input.length){
            return result;
        }
        //因为只需要输入最小的K个数字就直接i<k
        for (int i=0;i<k;i++){
            {    //确保每次循环结束最右边都是最小值
                for(int j=0;j<input.length-i-1;j++){
                    //比较j的位置和j+1的位置，将小的值后移
                    if(input[j]<input[j+1]){
                        int temp = input[j];
                        input[j]=input[j+1];
                        input[j+1]=temp;
                    }
                }
                //此时将冒泡最小的数字已经在数组的最右边，将这个数字添加到最后输出的数组中
                result.add(input[input.length-i-1]);
            }
        }
        return result;
    }
}

 

二、Arrays的sort函数

使用Arrays的sort函数直接排序之后再选择输出

import java.util.Arrays;
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> result= new ArrayList<Integer>();
        //当输入数组为空，或者输入数组长度小于k的值返回为null
        if(input.length==0||k<=0||k>input.length){
            return result;
        }
        Arrays.sort(input);
        //因为只需要输入最小的K个数字就直接i<k
        for (int i=0;i<k;i++){
            {    
                result.add(input[i]);
            }
        }
        return result;
    }
}

三、使用TreeSet排序并去重元素

import java.util.Arrays;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.TreeSet;
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> temp= new ArrayList<Integer>();
        ArrayList<Integer> result= new ArrayList<Integer>();
        //当输入数组为空，或者输入数组长度小于k的值返回为null
        if(input.length==0||k<=0||k>input.length){
            return result;
        }
        //利用TreeSet排序并去重元素
       TreeSet<Integer> set=new TreeSet<Integer>();
        for(int i:input){
            set.add(i);
            //为了适应海量数据去重，确保set中存储的只有k个，而且已经是有顺
            if(set.size()>k){
                set.remove(set.last());
            }
        }
        Iterator<Integer> iterator= set.iterator();
        while(iterator.hasNext()){
            int x=iterator.next();
            temp.add(x);
        }
        //因为只需要输入最小的K个数字就直接i<k
        for (int i=0;i<k;i++){
            {    
                result.add(temp.get(i));
            }
        }
        return result;
    }
}