《剑指offer》Java实现--找出最小的K个数

题目描述

    给定一个无序数组，输出其中最小的K个数。

思路分析

    首先大家最容易想到的就是先对数组进行升序排序，然后输出前K个数，这样的时间复杂度为nlog(n)，如果排序算法选的好，也许还有提高。但nlog(n)的时间复杂度面试官一般是不会满意的，毕竟这个方法大多数人都会想到。
    另一种解题思路，我们基于快排中的Partition思想来实现。如果基于数组的第k个数来调整，则使得比第k个数字小的数字都位于它的左边，大的都位于它的右边。如此调整后位于数组左边的k个数字就是最小的k个数了，时间复杂度为O(N)。注意：此种方法不保证输出的数字有序，并且会改变原有数组。

Java代码实现

import java.util.Stack;

/**
 * 获取给定数组中最小的K个数
 * @author Administrator
 * @version 2018/10/23
 */
public class Exe42_GetMinestKNum {
    
    public static void main(String[] args) {
        
        int[] datas={4,5,1,6,2,7,3,8};
        getMinestKNumByPartition(datas, 4);
        
    }
    
    //解法一：借用快排思想
    public static void getMinestKNumByPartition(int[] datas,int k) {
        
        if(datas==null||k>datas.length){
            return;
        }else {
            int start=0;
            int end=datas.length-1;
            int tempK=partition(datas, start, end);
            while(tempK!=k-1){
                if(tempK>k-1){
                    end=tempK-1;
                    tempK=partition(datas, start, tempK-1);
                }else{
                    start=tempK+1;
                    tempK=partition(datas, start, end);
                }
            }
            for(int i=0;i<k;i++){
                System.out.print(datas[i]+" ");
            }
        }
        
    }
    
    private static int partition(int[] datas,int start,int end) {
        if(datas==null||start<0||start>datas.length-1||end<start||end>datas.length-1){
            return -1;
        }else {
            int midIndex=start;
            start++;
            while(start<end){
                while(datas[end]>datas[midIndex]&&start<end){
                    end--;
                }
                while(datas[start]<=datas[midIndex]&&start<end){
                    start++;
                }
                swap(datas, start, end);
            }
            swap(datas, start, midIndex);
            return start;
        }
    }
    
    private static void swap(int[] datas,int index1,int index2) {
        if(datas==null||index1<0||index1>datas.length-1||index2<0||index2>datas.length-1){
            return;
        }else {
            int temp=datas[index1];
            datas[index1]=datas[index2];
            datas[index2]=temp;
        }
        
    }
    
    //解法二：借用最大(小)堆思想
    public static void getMinestKNumByStack(int[] datas,int k) {
        
        if(datas==null||datas.length<k){
            return;
        }else {
            Stack<Integer> aidStack=new Stack<Integer>();
        }
        
    }

}

不允许修改数组

    如果面试关明确要求不允许修改数组呢，那上面的i思路就行不通了；此外，如果数据量过大，上面的解法也会显得无能为力；此时我们可以借助堆排序的思想或直接使用堆排序来实现。