剑指 Offer.40-把数组排成最小的数

剑指 Offer.40-最小的k个数

题目链接

问题描述

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

个人解法

直接通过库函数对数据进行排序，排序后直接返回最小的k个数字即可（面试中不可用）

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        int[] res = new int[k];
        // 通常在面试中不能够使用库函数
        Arrays.sort(arr);

        for(int i=0;i<k;i++){
            res[i] = arr[i]; 
        }

        return res;
    }
}

进阶解法

手写排序算法实现，排序后直接返回最小的k个数字即可（推荐手动实现快速排序）大数据情况下不适用（当数据多到超过内存，该方案不能用）

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        // 手搓快速排序
        quickSort(arr,0,arr.length-1);
        return Arrays.copyOf(arr,k);
    }

    private void quickSort(int[] arr,int l,int r){
        // 递归出口
        if(l >= r) return;
        int i = l, j = r;
        // 两指针向中间扫描
        while(i<j){
            //扫描从后开始找小的元素
            while(i < j && arr[j] >= arr[l]) j--;
            //从前开始找大的元素
            while(i < j && arr[i] <= arr[l]) i++;
            swap(arr,i,j);
        }
        //将哨兵元素放在其对应位置
        swap(arr,i,l);
        quickSort(arr,l,i-1);
        quickSort(arr,i+1,r);
    }

    // 辅助快排的交换函数
    private void swap(int[] arr,int i,int j){
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

推荐解法

使用堆或者红黑树进行实现，由于目前个人对红黑树了解不深，尝试使用最大堆进行实现，该方案可应对大数据场景下，该需求的应用

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if(k > arr.length) return arr;
        if(k == 0) return new int[0];
        int[] res = new int[k]; 
        //构建最大堆
        Queue<Integer> heap = new PriorityQueue<Integer>(k,Comparator.reverseOrder());
        for(int i=0;i<arr.length;i++){
            if(heap.size() < k){
                heap.add(arr[i]);
            }else if(heap.size() >= k){
                if(arr[i] > heap.peek()){
                    continue;
                }else{
                    heap.poll();
                    heap.add(arr[i]);
                }
            }
        }
        for(int i=0;i<k;i++){
            res[i] = heap.poll();
        }
        return res;
    }
}

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。