剑指Offer:面试题30——最小的k个数(java实现)

问题描述：

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

思路1：

先排序，再取前k个
时间复杂度O(nlogn)

下面给出快排序的代码（基于下面Partition函数的方法）

public void QuickSort(int[] arr, int start, int end){

    if(start == end){
        return;
    }
    int index = Partition(arr, start, end);

    if(index > start){
        QuickSort(arr, start, index - 1);
    }
    if(index < end){
        QuickSort(arr, index + 1, end);
    }
}

相应的求最小的k个数的代码：

static boolean InvalidInput = false;
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {


        ArrayList<Integer> result = new ArrayList<Integer>();
        if(input == null || input.length == 0 || k > input.length || k <= 0){
            InvalidInput = true;
            return result;
        }


        int start = 0;
        int end = input.length - 1;
        QuickSort(input, start, end);

        for(int i = 0; i < k; i++){
            result.add(input[i]);
        }

        return result;
    }

思路2：（适合海量数据的输入）

—维护一个大小为k的容器。
—每次从输入整数读取一个数，如果容器中的数字少于k个，则直接加入，否则，找出容器中的最大值，与当前数字比较，若大于最大值，则不管，若小于，则替换最大值。
—时间复杂度O(n*log*k)

关于容器的数据结构的选择：

数组：查找最大值需要O(k)
最大堆：查找最大值需要O(1),但需要O(logk)时间完成删除及插入操作。
红黑树

思路3：基于Partition,会改变原始数组

首先来看看Partition的原理与具体实现以及结果

Partition:思想是随机选择一个数，调整数组使得比所选数小的数字移动到数组的左边，比选择的数字大的数字大的数移到数组的右边。上一文中也用到了Partition的思想，但是并没有弄懂。下面对代码进行了详细的注释。

基于上述Partition函数的解析，我们能用它来实现本文中的求最小的k个数

思想：如果基于数组的第k个数字来调整，使得比第k个数字小的所有数字都位于数组的左边，比第k个数字大的数字都位于数组的右边。这样调整后，位于数组中左边的k个数字就是最小的k个数字。
缺陷：会改变原始数组;所得到的k个最小的数字不是有序的。

代码：

import java.util.ArrayList;

public class Solution {
    static boolean InvalidInput = false;
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {


        ArrayList<Integer> result = new ArrayList<Integer>();
        if(input == null || input.length == 0 || k > input.length || k <= 0){
            InvalidInput = true;
            return result;
        }


        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++){
            result.add(input[i]);
        }

        return result;
    }


    public int Partition(int[] arr, int start, int end){
        if(arr == null || arr.length == 0 || start < 0 || end < 0){
            return -1;
        }

        int index = start + (int)(Math.random() * ((end - start) + 1));//随机选择一个作为标杆的数字


        //将标杆放在数组最后一位
        int tmp = arr[index]; arr[index] = arr[end]; arr[end] = tmp;

        int small = start - 1;//small用来存储从右到左第一个小于标杆的数字的下标
        for(index = start; index < end; index++){
            if(arr[index] < arr[end]){//如果小于标杆
                small++;//更新第一个小的
                if(small != index){//如果当前遍历的不是第一个小的
                    tmp = arr[index];arr[index] = arr[small];arr[small] = tmp;//将当前遍历的数字放在第一个小的位置上

                }
            }
        }

        //由于small指示的是从右到左第一个小于标杆的，而此时标杆还放在数组最后，因此，应该将标杆放在small后面一位。
        small++;
        tmp = arr[small];arr[small] = arr[end]; arr[end] = tmp;

        return small;//返回位置为所选择的标杆最后的位置


    }
}