每日一题之《剑指offer》29题

第二十九题：最小的k个数

难易度：⭐⭐⭐

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

我相信，所有的人看到这道题目最开始无脑的想法就是先排序，然后再遍历前k个元素，虽然无脑，不过快排的partition也是本题的核心思想，不妨动手写一下回顾下快排的代码：
代码如下：

import java.util.ArrayList;

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        if(input == null || input.length == 0 || k <= 0 || k > input.length){
            return arrayList;
        }
        sort(input,0,input.length - 1);
        for(int i = 0;i < k;i++){
            arrayList.add(input[i]);
        }
        return arrayList;
    }
    
    public static void sort(int[] arr,int l,int r){
        if(l < r){
            int[] indexArr = partition(arr,l,r);
            sort(arr,l,indexArr[0] - 1);
            sort(arr,indexArr[1] + 1,r);
        }
    }
    
    public static int[] partition(int[] arr,int l,int r){
        int p1 = l-1;
        int p2 = r;
        int cur = l;
        while(cur < p2){
            if(arr[cur] < arr[r]){
                swap(arr,cur++,++p1);
            }else if(arr[cur] > arr[r]){
                swap(arr,cur,--p2);
            }else{
                cur++;
            }
        }
        swap(arr,r,p2);
        return new int[]{++p1,--p2};
    }
    
    public static void swap(int[] arr,int i,int j){
        if(i == j){
            return;
        }
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }
}

如果先对数组进行排序，然后再取前k个值，这种方法因为需要对整个数组进行排序，所以时间复杂度为：O(nlogn)。

既然涉及到了快排，其实我们不难想到可以利用partition来求前k个值。因为partition就是将某一个值在排序后数组的位置找出来，在这个值的前面就是比这个值小的数，在这个值的后面即是比这个数大的数。通过partition过程可以对上述的代码进行改进：
代码如下：

import java.util.ArrayList;

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        if(input == null || input.length == 0 || k <= 0 || k > input.length){
            return arrayList;
        }
        int index = partition(input,0,input.length - 1);
        while(index != k - 1){
            if(index < k - 1){
                index = partition(input,index + 1,input.length - 1);
            }else{
                index = partition(input,0,index - 1);
            }
        }
        for(int i = 0;i < k;i++){
            arrayList.add(input[i]);
        }
        return arrayList;
    }
    
    
    public static int partition(int[] arr,int l,int r){
        int p1 = l-1;
        int p2 = r;
        int cur = l;
        while(cur < p2){
            if(arr[cur] < arr[r]){
                swap(arr,cur++,++p1);
            }else if(arr[cur] > arr[r]){
                swap(arr,cur,--p2);
            }else{
                cur++;
            }
        }
        swap(arr,r,p2);
        return p2;
    }
    
    public static void swap(int[] arr,int i,int j){
        if(i == j){
            return;
        }
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }
}

上述代码的思路则是利用了快排中的patition,基于数组中第k个数字来进行调整，调整之后比第k个数字小的数就都位于数组的左边，比k个数字大的数就都位于数组的右边，当然者k个数组不一定是按照顺序排列的，本思想的时间复杂度为 O(n).

除了上述的方法，本题还可以使用最大堆这种结构来完成需求，定义一个长度为k的堆，往堆里加数，每次都和堆顶进行比较，如果比堆顶小，那么删除堆顶，让新的数字进入到堆中，这样遍历完一边数组后，最大堆中保存的就是最小的k个数

每日一题之《剑指offer》29题

第二十九题：最小的k个数

全站热榜