最小的K个数 剑指offer

题目描述

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

思路：快速排序的思想，

分析：

方法一，用快速排序的partition()方法，寻找分割点

通过一趟排序将要排序的数据分割成独立的两部分，分割点左边都是比它小的数，右边都是比它大的数。

分割点及其左边的数字构成一个数组A，数组长度为index+1;

1.1  当理想情况是index+1=k,说明刚好是该数组A；

1.2   index+1>k,说明需要的k个数字在分割点左边；需要剔除分割点，在左边数组继续寻找；

if(index>k-1){
                end=index-1;

 index=partition(input,start,end);}

1.3   index+1<k,说明需要的k个数字不仅包含A，而且还有分割点右边最小的若干个数字，需要继续寻找

{
                start=index+1;
                index=partition(input,start,end);
            }

需要注意的是，分割点左右两边的数字都是没有排序的。 

例如：输入4,5,1,6,2,7,3,8这8个数字,分割点为4，

1）一次循环后，数组变为3，2，1，4，6，7，5，8，需要最小的5个数，所以3，2，1，4 不满足，需要在 4的右边继续寻找；

2）对arr（start+1，end），6，7，5，8即使用partition()方法，得到5，6，7，8，arr={3，2，1，4,  5，6，7，8), 分割点为6所在的位置，所以index=5 ,5>k-1;属于1.2的情形

核心：partition()方法

 /**
     * 初始化分割点arr[start]
     * @param arr
     * @param start  分割数组的起始位置
     * @param end  分割数组的结束位置
     * @return 返回分割点在分割后数组的位置
     */
        private int partition(int[] arr, int start,int end){
            int pivotKey=arr[start];
            while(start<end){
                while(start<end && arr[end]>=pivotKey)
                    end--;
                arr[start]=arr[end];
                while(start<end && arr[start]<=pivotKey)
                    start++;
                arr[end]=arr[start];
            }
            arr[start]=pivotKey;
            return start;
        }

 实现代码：

  public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
 ArrayList<Integer> leastNumbers = new ArrayList<Integer>();//定义输出数组
        while(input==null || k<=0 || k>input.length)
            return leastNumbers;
        int start=0;
        int end=input.length-1;
        int index=partition(input,start,end);//分割点的位置index
        while(index!=k-1){
            if(index>k-1){
                end=index-1;
                index=partition(input,start,end);
            }else{
                start=index+1;
                index=partition(input,start,end);
            }
        }
        for(int i=0;i<k;i++){//满足要求的数组，存入输出数组
            leastNumbers.add(input[i]);
        }
        return leastNumbers;
    }

含有测试用例的完整代码：

import java.util.ArrayList;
public class Error1 {
        public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
            ArrayList<Integer> leastNumbers = new ArrayList<Integer>();
            while(input==null || k<=0 || k>input.length)
                return leastNumbers;
            int start=0;
            int end=input.length-1;
            int index=partition(input,start,end);
            while(index!=k-1){
                if(index>k-1){
                    end=index-1;
                    index=partition(input,start,end);
                }else{
                    start=index+1;
                    index=partition(input,start,end);
                }
            }
            for(int i=0;i<k;i++){
                leastNumbers.add(input[i]);
            }
            return leastNumbers;
        }

    /**
     * 初始化分割点arr[start]
     * @param arr
     * @param start  分割数组的起始位置
     * @param end  分割数组的结束位置
     * @return 返回分割点在分割后数组的位置
     */
        private int partition(int[] arr, int start,int end){
            int pivotKey=arr[start];
            while(start<end){
                while(start<end && arr[end]>=pivotKey)
                    end--;
                arr[start]=arr[end];
                while(start<end && arr[start]<=pivotKey)
                    start++;
                arr[end]=arr[start];
            }
            arr[start]=pivotKey;
            return start;
        }
    public static void main(String[] args) {
        Error1 s=new Error1();
        int[] a={4,5,1,6,2,7,3,8};
        int k=5;
        ArrayList<Integer> result=s.GetLeastNumbers_Solution(a,k);
        for(Integer i:result)
            System.out.println(i);
    }

}

方法二、最大堆的思想 

代码结构更加简单

import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Comparator;
public class Solution {
        public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
            ArrayList<Integer> result = new ArrayList<Integer>();
            int length = input.length;
            if(k > length || k == 0){
                return result;
            }
            /**
             * PriorityQueue是一个比较标准的队列实现类
             * 默认从小到大排列
             */
            PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(k, new Comparator<Integer>() {

                @Override
                public int compare(Integer o1, Integer o2) {
                    return o2.compareTo(o1);//按照从大到小
                }
            });
            /**
             * 不等于k的时候，一直增加到k个元素
             * 等于k的时候，用最大值反复比较，替换
             */
            for (int i = 0; i < length; i++) {
                if (maxHeap.size() != k) {
                    maxHeap.offer(input[i]);//插入队列
                } else if (maxHeap.peek() > input[i]) {//此方法返回此列表或栈顶的头元素，或null，如果此列表为空，查看列表或栈顶的对象而不移除它。
                    Integer temp = maxHeap.poll();//从队列中取出一个元素，但是 poll() 在获取元素失败的时候会返回空
                    temp = null;
                    maxHeap.offer(input[i]);
                }
            }
            for (Integer integer : maxHeap) {
                result.add(integer);
            }
            return result;
        }
}