最小的K个数 java实现 剑指offer

题目描述

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

解题思想：
原来的做题思路是直接快速排序法排一遍，在取出这最小的K个数，可行，但是有些排序多余了，因为这边只要找到最小的K个数，快排的话会整体排一遍，次数可能大于K次，所以这边采用最小堆排序的方法，只需要排k次即可取出最小的K个数。

import java.util.*;

public class Solution {
    private int[] data;
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> list=new ArrayList<Integer>();
        data=input;
        int len=input.length;
        int end=len-1;
        if(k>end+1||k==0)//特殊情况，输入的K为0或者k>数组长度
            return list;
        for(int i=0;i<k;i++){
            createMinHeap(end-i);
            swap(0,end-i);
            list.add(data[end-i]);
        }
        return list;
    }
    public  void createMinHeap(int end){
        if(end==0) return;
        int index=(end-1)/2;
        for(int i=index;i>=0;i--){//每次循环找出一棵树中最小的值，并将这个值放在根节点处
            int k=i;
            int smaller=data[i];
            if(2*i+1<=end){
                if(data[2*i+1]<smaller){//左节点存在
                    k=2*i+1;
                    smaller=data[2*i+1];
                }
                    
                if(2*i+1<end){//右节点存在
                    if(data[2*i+2]<smaller)
                        k=2*i+2;
                }
            }
            if(k!=i) swap(i,k);
        }
    }
    public void swap(int n1,int n2){
        int temp=data[n1];
        data[n1]=data[n2];
        data[n2]=temp;
    }
}