剑指 Offer 40.最小的k个数

剑指 Offer 40.最小的k个数

剑指 Offer 40.最小的k个数

设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。

示例：
输入： arr = [1,3,5,7,2,4,6,8], k = 4
输出： [1,2,3,4]

提示：
0 <= len(arr) <= 100000
0 <= k <= min(100000, len(arr))

---

思路一

将数组从小到大排序，然后取出前k个元素即可

class Solution {
    public int[] smallestK(int[] arr, int k) {
        //边界条件
        if(arr == null || arr.length == 0) return arr;
        if(k < 0 || k > arr.length) return null;
        //排序
        Arrays.sort(arr);
        //从原数组中，取出[0, k)个元素，组成新的数组
        return Arrays.copyOfRange(arr, 0, k);
    }
}

思路二

利用快速排序的思路
能用快排的原因，题目里面有【以任意顺序】 步骤

随便找个数，进行一轮快排
快排结束，进行数据划分,假设这个数属于第t个
t==k，那么返回前t个；
t > k，那么问题规模缩小为在前面t-1个数找k个；
t < k，说明已经确定前t个数属于前k个，但是第t+1到k这些数还没确定，那么问题规模缩小为从t+1到右边界找k-t个数

需要注意的是，“那么问题规模缩小为从t+1到右边界找k-t个数”，传值的时候还是k，不能写成k - t
因为，k = t这个条件是一直不变的，k是固定的

class Solution {
    public int[] smallestK(int[] arr, int k) {
        //边界条件
        if(k == 0) return new int[0];
        if(arr == null || arr.length == 0) return arr;
        if(k < 0 || k > arr.length) return null;

        findTruePivot(arr, 0, arr.length - 1, k);

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

        return resultArray;
    }

    //找到t = k的时机，此时机下的数组前k个，即是要求的结果
    public static void findTruePivot(int[] arr, int begin, int end, int k){
        //边界条件
        if(begin >= end){
            return;
        }

        int t = findPivotIndex(arr, begin, end);
        if(t == k){
            //此时数组满足条件
            return;
        }else if(t < k){//说明左边的要，右边还差k - t个
            //需要说明的是，t + 1, end都是以arr为下标
            //k不能变（也就是不能写成k - t）
            findTruePivot(arr, t + 1, end, k);
        }else if(t > k){//说明下一步需要找[0, t - 1];
            findTruePivot(arr, begin, t - 1, k);
        }
    }

    //查找轴点
    public static int findPivotIndex(int[] arr, int begin, int end){
        //[begin, end]左闭右闭
        //将第一个值存起来
        int pivotValue = arr[begin];

        while(begin < end){
            while(begin < end){
                if(pivotValue < arr[end]){
                    end--;
                }else{
                    arr[begin] = arr[end];
                    begin++;
                    break;
                }
            }

            //调个
            while(begin < end){
                if(arr[begin] < pivotValue){
                    begin++;
                }else{
                    arr[end] = arr[begin];
                    end--;
                    break;
                }
            }
        }

        //此时begin = end
        arr[begin] = pivotValue;
        return begin;
    }
}