剑指offer40题最小的K个数

第40题：//输入整数数组 nums ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
// 示例 1：
//
// 输入：nums = [3,2,1], k = 2
//输出：[1,2] 或者 [2,1]
// 示例 2：
//
// 输入：nums = [0,1,2,1], k = 1
//输出：[0]
// 限制：
//
//
// 0 <= k <= nums.length <= 10000
// 0 <= nums[i] <= 10000
// Related Topics 堆 分治算法
解题思路：
快排变形的方法：（分治）找第K大的数或找前K个大的数都可以用快排选择算法。快速选择算法与快速排序算法的区别在于快速选择算法只需要递归地选择一侧的数组，快速选择算法在本题中我们只需要知道最小的K个数是哪些，并不需要知道它们排序，可以看作是一个不完全的快速排序。我们在进行一次分治后，比如说我们的分割的位置在m,m左边的数都比m小，m右边的数都比m大。所以：
1.若K=m，这样就直接找到了小于k的数。
2.若k<m,则说明k在m以内，在m的左侧数组，我们只需对左侧数组递归就可以。
3.若k>m,则说明中左侧数组中的m个数属于最小的K个数，所以我们还需对右侧数组去寻找最小的k-m个数。对右侧数组进行递归。
具体代码如下：

import java.util.Arrays;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int[] getLeastNumbers(int[] nums, int k) {
        if (k == 0) {
            return new int[0];
        } else if (nums.length <= k) {
            return nums;
        }
        partitionArray(nums, 0, nums.length - 1, k);
        // 数组的前 k 个数此时就是最小的 k 个数，将其存入结果
        int[] res = new int[k];
        for (int i = 0; i < k; i++) {
            res[i] = nums[i];
        }
        return res;
    }

    void partitionArray(int[] nums, int lo, int hi, int k) {
        int m = quickselect(nums, lo, hi);
        if (k == m) {
            // 正好找到最小的 k(m) 个数
            return;
        } else if (k < m) {
            // 最小的 k 个数一定在前 m 个数中，递归划分
            partitionArray(nums, lo, m - 1, k);
        } else {
            // 在右侧数组中寻找最小的 k-m 个数
            partitionArray(nums, m + 1, hi, k);
        }
    }

    int quickselect(int[] nums, int start, int end) {
        /*循环找比标准数大的数和比标准数小的数*/
            /*把数组中的第0个数字作为标准数*/
            int stard = nums[start];
            /*记录需要排序的下标*/
            int low = start;
            int high = end;
            while (low < high) {
                /*右边的数字比标准数大*/
                while (low < high && stard <= nums[high]) {
                    high--;
                }
                /*使用右边的数字替换左边的数*/
                nums[low] = nums[high];
                /*如果左边的数字比标准数小*/
                while (low < high && nums[low] <= stard) {
                    low++;
                }
                nums[high] = nums[low];
            }
            /*把标准数赋给低所在的位置的元素*/
            nums[low] = stard;
        return low;
        }

    }