面试题 30

1 题目描述

输入 n 个整数，找出其中最小的 k 个数

2 算法描述

利用快速排序找到序列中排名为 k 的数字，其左边的数字均小于该数子。

3 java实现

public class GetLeastNumbers{
    public static void main(String[] args) {
        getLeastNumbers(new int[]{1,2,3,3,2,3,3,0},5);
    }

    public static void  getLeastNumbers(int[] arrays,int k){
        if(arrays!=null&&arrays.length<=k){
            throw new RuntimeException();
        }
        int start=0;
        int end=arrays.length-1;
        int index=partition(arrays,start,end);
        while(index!=k){
            if(index>k){
                index=partition(arrays,start,index-1);
            }else{
                index=partition(arrays,index+1,end);
            }
        }
        for(int i=0;i<k;i++){
            System.out.println(arrays[i]);
        }   
    }
    public static int partition(int[] arrays,int start,int end){
        int pivot=arrays[start];
        int temp_1;
        while(start<end){
            while(arrays[end]>=pivot&&end>start) end--;
            temp_1=arrays[end];
            arrays[end]=arrays[start];
            arrays[start]=temp_1;
            while(arrays[start]<=pivot&&end>start) start++;
            temp_1=arrays[start];
            arrays[start]=arrays[end];
            arrays[end]=temp_1;
        }
        return end; 
    }
}

4 其他算法

上面的算法需要改变数组的结构
我们可以首先创建一个大小为 k 的数据容器来存储最小的 k 个数字，接下来我们每次从输入的 n 个整数中读取一个数。如果容器中已有的数字少于 k 个，则直接把这次读入的整数放入容器之中，如果容器中已有 k 个数字了，也就是容器已满，此时需要替换已有的数字，找出已有的 k 个数中的最大值，然后那这次带插入的整数和最大值进行比较。
当容器满了之后，我们需要做三件事，找到 k 个数中最大的数字，删除容器中最大的数字，插入新的数字。