题解 | #最小的K个数#

#include <queue>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param input int整型vector
     * @param k int整型
     * @return int整型vector
     */

    void adjuct(vector<int>& arr,int len, int index) {
        //判断是不是父节点
        while (index <= len / 2 - 1) {
            //如果是，则判断只有左孩子还是，有两个孩子
            //有两个孩子
            if (index * 2 + 2 <= len - 1) {
                index = arr[index * 2 + 1] < arr[index * 2 + 2] ? index * 2 + 1 : index * 2 + 2;

            } else { //有一个孩子
                index = index * 2 + 1;
            }

            if (arr[index] < arr[(index + 1) / 2 - 1]) {
                swap(arr[index], arr[(index + 1) / 2 - 1]);
            } else {
                break;
            }
        }

    }
    vector<int> GetLeastNumbers_Solution(vector<int>& input, int k) {
        // write code here
        //错误处理
        
        if (input.size() == 0 || k <= 0)return vector<int>();

        //使用堆排序
        //1.建立堆小顶堆

        int range_father = input.size() / 2 - 1;
        for (int i = range_father; i >= 0; i--) {
            adjuct(input, input.size(), i);
        }
        //取出k个最小值
        vector<int> res;
        int target = input.size() - 1 - k;
        for (int i = input.size() - 1; i > target; i--) {
            
            swap(input[0], input[i]);
            res.push_back(input[i]);
            adjuct(input, i, 0);
        }
        return res;
    }
};
题解一：该题可以使用堆排序，通过小顶堆，获取每k个最小的值，时间复杂度是O(nlogn),空间复杂度是O(1)。