【面试题29-最小的k个数】

剑指offer第二九题。

题目描述

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

解题思路

对于这种不变的数组，第一种思路是快速排序，然后找出前几个数即可，这种方法的时间复杂度为nlogn。

第二种更优的思路是堆排，因为找到前k个数字的时间复杂度为nlogk

我的答案

快速排序：

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> res = new ArrayList<>();
        if(k > input.length || k == 0){
            return res;
        }
        
        //快排
        quick_sort(input,0,input.length-1);
        
        for(int i=0;i<k;i++){
            res.add(input[i]);
        }
        
        return res;
    }
    
    //只要low<high就满足递归条件
    private void quick_sort(int[] arr,int low,int high){
        if(low < high){
            //三色国旗，每次partion之后实现将小于基准数和大于基准数的值想办法搞到两边去
            //返回的数组是一个长度为2的数组，分别放等于基准数的起始坐标和终止坐标
            int[] p = partion(arr,low,high);
            //对小于基准数的地方再次递归来搞成三色国旗
            quick_sort(arr,low,p[0]-1);
            //对大于基准数的地方也再次递归搞成三色国旗
            quick_sort(arr,p[1]+1,high);
        }
    }
    
    //三色国旗，尤其注意的是下标
    private int[] partion(int[] arr,int low,int high){
        int less = low - 1;
        int more = high + 1;
        int curr = low;
        int num = arr[curr];
        while(curr < more){
            //小于基准值则跟++less交换，大于基准值则跟--more交换，相等则不管，继续前进
            if(arr[curr] < num){
                swap(arr,++less,curr++);
            }else if(arr[curr] > num){
                swap(arr,curr,--more);
            }else{
                curr++;
            }
        }
        return new int[]{less,more};
    }
    
    private void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

原生堆排来实现：

import java.util.ArrayList;
public class Solution {
    ArrayList<Integer> res = new ArrayList<>();
    
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        //由于是找前k个数字，是比较小的，所以适合用小跟堆来解决
        //因为大根堆先得到的是最大值，时间复杂度无法达到理想的nO(k)
        //整个过程是对数组进行操作的，但是与操作一颗二叉树是一样的，因为二叉堆是可以用数组来表示的
        //数组的第一个元素就是二叉堆的root
        //我们要保证是最小堆，那么每次从root拿到的数必然是最小的数
        //root提取出来之后，将root和最后一个数交换后需要重新调整堆维持堆的性质
        
        if(k == 0 || k > input.length){
            return res;
        }
        
        heapSort(input,k);
        
        return res;
    }
    
    private void heapSort(int[] arr,int k){
        if(arr == null || arr.length < 2){
            return;
        }
        
        //初步构建起一个最小堆，此时root是最小的一个数
        for(int i=0;i<arr.length;i++){
            heapInsert(arr,i);
        }
        
        int heapSize = arr.length;
        swap(arr,0,--heapSize);
        //将最小的数此时也放进list中，如果k恰好为1那么直接返回
        res.add(arr[heapSize]);
        if(res.size() == k){
            return;
        }
        
        while(heapSize > 0){
            //在对[0,heapSize]间构建最小堆，每一轮都找到最小值，然后交换到最后
            heapify(arr,0,heapSize);
            swap(arr,0,--heapSize);
            //每次都将堆中最小的数拿到heapSize索引处，所以直接添加进结果集中，结果集大小为k了则立即结束
            res.add(arr[heapSize]);
            if(res.size() == k){
                return;
            }
        }
    }
    
    //初步构建最小堆，即构建完毕之后root为堆中最小值
    private void heapInsert(int[] arr,int i){
        while(arr[i] < arr[(i-1)/2]){
            //如果比它的父亲小则与父亲交换
            swap(arr,i,(i-1)/2);
            i = (i-1)/2;
        }
    }
    
    
    //上浮过程，每次将root和最后一个数字进行交换，然后重新构建最小堆
    private void heapify(int[] arr,int index,int heapSize){
        int left = index * 2 + 1;
        while(left < heapSize){
            //如果右子节点也没有越界的话，则从左右中挑出一个最小值
            int largest = left+1 < heapSize && arr[left+1]<arr[left] ? left+1 : left;
            //再与当前结点做比较
            int maxIndex = arr[index] < largest ? index : largest;
            //最小的就是index的话，则不用再比较了，已经是最小值了
            if(maxIndex == index){
                break;
            }
            //不是的话，则要进行交换
            swap(arr,index,largest);
            index = maxIndex;
            left = index * 2 + 1;
        }
    }
    
    private void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}