剑指 Offer 40. 最小的k个数【31】

Myth丶恋晨 2023-09-27 12:21 131阅读 0赞

> **难度等级：简单**

> **上一篇算法：**
> 
> [剑指 Offer 44. 数字序列中某一位的数字【数学】][Offer 44.]

> **力扣此题地址：**
> 
> [剑指 Offer 40. 最小的k个数 - 力扣（LeetCode）][Offer 40. _k_ - _LeetCode]

### 1.题目：最小的k个数 ###

输入整数数组 `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.解题思路: ###

> **思路：快速排序加判断**
> 
> **找出其中最小的 k 个数，**这句话隐藏着以下几个意思：
> 
>  *  1、找出的这 k 个数并不需要按照顺序排列。
>  *  2、如果一开始就知道某个数不在这 k 个数中，完全可以将它丢到一旁。

> 也就意味着，在排序过程中，我们可以去不断的缩小排序的区间，这里我们借助**快速排序**的代码，稍微的改动几行就完成了这道题目。
> 
> 具体操作如下：
> 
>  *  1、以当前区间的第一个元素为基准元素 `pivot`，根据快速排序的操作，将当前区间划分为了三个区间。
>  *   *  1、左侧区间均是小于等于基准元素 `pivot` 的元素
>      *  2、中间区间均是等于基准元素 `pivot` 的元素
>      *  3、右侧区间均是大于等于基准元素 `pivot` 的元素
> 
>  *  2、对比基准元素 `pivot` 所在的下标 index 与 k 的关系
>  *   *  1、**index 小于 k**，说明从 0 到 index 这个左侧区间中的元素**不足 k 个**，那么最小的 `k` 个数肯定**部分**是在这个区间，还需要继续在右侧区间中去寻找出一部分元素来填充，因此对对右侧区间进行快速排序即可
>      *  2、**index 等于 k**，说明从 0 到 index 这个区间中的所有元素就是那些最小的 `k` 个数，将其返回。
>      *  3、**index 大于 k**，说明从 0 到 index 这个左侧区间中的元素**超过了 k 个**，那么最小的 `k` 个数肯定是都在在这个区间，而中间、右侧区间均可以不去处理，只需要继续对左侧区间进行快速排序即可，找到那 k 个数。

### 3.代码实现： ###

class Solution {
        public int[] getLeastNumbers(int[] arr, int k) {
    
            if (k == 0 || arr.length == 0) {
                return new int[0];
            }
    
            // 执行快速排序操作，定位找到下标为 k - 1 的那个元素
            return quickSort(arr,0,arr.length - 1,k - 1);
        }
    
    
        // 函数传入待排序数组 nums
        // 排序区间的左端点 left
        // 排序区间的右端点 right
        private int[] quickSort(int[] nums,int left, int right , int index){
    
            // 调用函数 partition，将 left 和 right 之间的元素划分为左右两部分
            int mid = partition(nums,left,right);
    
            // 如果 mid 下标恰巧为 index，那么找到了最小的 k 个数
            if (mid == index) {
                // 直接返回
                return Arrays.copyOf(nums, mid + 1);
    
            // 如果 mid 下标大于 index，那么说明需要在左侧元素中去切分
            }else if( mid > index ){
    
                // 对 mid 左侧的元素进行快速排序
                return quickSort(nums,left,mid - 1, index );
            }else{
    
                // 对 mid 右侧的元素进行快速排序
                return quickSort(nums,mid + 1,right, index );
            }
    
        }
    
        private int partition(int[] nums, int left ,int right){
    
            // 经典快速排序的写法
            // 设置当前区间的第一个元素为基准元素
            int pivot = nums[left];
    
            // left 向右移动，right 向左移动，直到 left 和 right 指向同一元素为止
            while( left < right ){
    
                // 只有当遇到小于 pivot 的元素时，right 才停止移动
                // 此时，right 指向了一个小于 pivot 的元素，这个元素不在它该在的位置上
                while( left < right && nums[right] >= pivot ){
                    // 如果 right 指向的元素是大于 pivot 的，那么
                    // right 不断的向左移动
                    right--;
                }
    
                // 将此时的 nums[left] 赋值为 nums[right]
                // 执行完这个操作，比 pivot 小的这个元素被移动到了左侧
                nums[left] = nums[right];
    
    
                // 只有当遇到大于 pivot left 才停止移动
                // 此时，left 指向了一个大于 pivot 的元素，这个元素不在它该在的位置上
                while( left < right && nums[left] <= pivot){
                    // 如果 left 指向的元素是小于 pivot 的，那么
                    // left 不断的向右移动
                    left++;
                }
    
                // 将此时的 nums[right] 赋值为 nums[left]
                // 执行完这个操作，比 pivot 大的这个元素被移动到了右侧
                nums[right] = nums[left];
    
            }
    
            // 此时，left 和 right 相遇，那么需要将此时的元素设置为 pivot
            // 这个时候，pivot 的左侧元素都小于它，右侧元素都大于它
            nums[left] = pivot;
    
            // 返回 left
            return left;
    
        }
    }

[Offer 44.]: https://blog.csdn.net/m0_51697147/article/details/127530527
[Offer 40. _k_ - _LeetCode]: https://leetcode.cn/problems/zui-xiao-de-kge-shu-lcof/