剑指 Offer 40. 最小的k个数(leetcode每日打卡)

题目描述

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

示例 1：

输入：arr = [3,2,1], k = 2 输出：[1,2] 或者 [2,1] 示例 2：

输入：arr = [0,1,2,1], k = 1 输出：[0]

思路

快速排序分组

题目只要求返回最小的 k 个数，对这 k 个数的顺序并没有要求。因此，只需要将数组划分为 最小的 k 个数 和 其他数字 两部分即可，而快速排序的哨兵划分可完成此目标。

根据快速排序原理，如果某次哨兵划分后 基准数正好是第 k+1 小的数字 ，那么此时基准数左边的所有数字便是题目所求的 最小的 k 个数 。

根据此思路，考虑在每次哨兵划分后，判断基准数在数组中的索引是否等于 k ，若 true 则直接返回此时数组的前 kk个数字即可。

若 k < i ，代表第 k+1 小的数字在 左子数组 中，则递归左子数组； 若 k > i ，代表第 k+1 小的数字在 右子数组 中，则递归右子数组； 若 k = i，代表此时 arr[k] 即为第 k+1 小的数字，则直接返回数组前 k 个数字即可；

题解

//输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if(k>=arr.length){return arr;}
        return quickSort(arr,0,arr.length-1,k);
    }
    public int[] quickSort(int[]arr, int left,int right,int k){
        int l=left;
        int r=right;
        int temp=arr[left];
        while(l<r){
            while(l<r && arr[r]>=temp){
                r--;
                }
            while(l<r && arr[l]<=temp){
                l++;
                }
            swap(arr,l,r);
        }
        swap(arr,left,l);
        if(k>l){return quickSort(arr,l+1,right,k);}
        if(k<l){return quickSort(arr,left,l-1,k);}
        return Arrays.copyOf(arr,k);

    }
    public void swap(int[] arr,int i,int j){;
        int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }
}

空间复杂度划分函数的平均递归深度为O(logN)

时间复杂度 总体时间复杂度为O(N)

添加备注

执行用时：2 ms, 在所有 Java 提交中击败了97.06%的用户

内存消耗：39.7 MB, 在所有 Java 提交中击败了57.95%的用户

通过测试用例：38 / 38