题目描述

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

解题思路

最简单的方法是，直接使用sort函数对输入数组进行排序，然后输出前k个元素。其时间复杂度为O(nlogn).

class Solution
{
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k)
    {
        vector<int> result;
        
        if (input.empty() || k<=0 || k > input.size())
            return result;
        sort(input.begin(), input.end());
        for (int i=0; i < k; i++)
        {
            result.push_back(input[i]);
        }
        return result;
    }
};

还有一种时间复杂度O(nlogk)的堆排序方法，要优于上述方法。

堆排序，分为大顶堆排序和小顶堆排序。堆排序适合海量数据的处理

堆是具有下列性质的完全二叉树：每个结点的值都大于或等于左右孩子的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。

首先构建一个二叉树型的数据容器，用于存放数组的前k个值。
- 然后对这k个值进行大顶堆构建，
- 然后将无序的大顶堆排序为有序的大顶堆
- 判断第k个之后的元素与数据容器中最后一个元素（即容器中最大的元素）进行比较
  - 若小于容器中最后一个元素，则进行交换，交换后重新构建大顶堆；
  - 否则跳过判断数组中下一个元素

class Solution
{
public:
    void HeadAdjust (vector<int> &input, int parent, int length)
    {
        int temp = input[parent];
        int child = 2*parent + 1; // 左树
        
        while (child<length)
        {
            if (child+1 < length && input[child] < input[child+1])// 判断左右树的大小
                child++; // 若条件成立，则说明右树大
            if (temp>=input[child]) // 若当前根结点大于等于最大左右子树，则直接跳出循环
                break;
            input[parent] = input[child]; // 将较大的子树结点赋值给当前根结点
            // 对下一层进行大顶堆排序
            parent = child;
            child = 2*parent +1;
        }
        input[parent] = temp; // 将原根结点的值赋值给替换的结点
    }
    
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k)
    {
        vector<int> result;
        if (input.empty() || k <= 0 || k > input.size())
        {
            return result;
        }
        
        // 遍历输入的n个整数
        for (int i=0; i < input.size(); i++)
        {
            if (result.size() < k) // 若result中的元素小于k时直接存放在result容器中
                result.push_back(input[i]);
            else
            {
                // 对result容器中k个元素进行大顶堆排序
                for (int j = k/2; j >= 0; j--)
                    HeadAdjust(result, j, k);  
                // 将无序的大顶堆进行有序排列,将堆顶与最后一个元素互换，然后对前k-1个元素进行大顶堆排序
                for (int j = k -1; j > 0; j--)
                {
                    swap(result[0],result[j]);
                    HeadAdjust(result, 0, j);
                }
                if (result[k-1] > input[i])
                    result[k-1] = input[i];
            }
        }
        return result;
    }
};

对堆排序方法的优化，因为当遍历到第k个元素之后，若没有跟新result容器中的元素时，不用每次都执行一次对result容器的堆排序等操作。做了以下调整：

class Solution
{
public:
    void HeadAdjust (vector<int> &input, int parent, int length)
    {
        int temp = input[parent];
        int child = 2*parent + 1; // 左树
        
        while (child<length)
        {
            if (child+1 < length && input[child] < input[child+1])// 判断左右树的大小
                child++; // 若条件成立，则说明右树大
            if (temp>=input[child]) // 若当前根结点大于等于最大左右子树，则直接跳出循环
                break;
            input[parent] = input[child]; // 将较大的子树结点赋值给当前根结点
            // 对下一层进行大顶堆排序
            parent = child;
            child = 2*parent +1;
        }
        input[parent] = temp; // 将原根结点的值赋值给替换的结点
    }
    
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k)
    {
        vector<int> result;
        bool change = true;
        if (input.empty() || k <= 0 || k > input.size())
        {
            return result;
        }
        
        // 遍历输入的n个整数
        for (int i=0; i < input.size(); i++)
        {
            if (result.size() < k) // 若result中的元素小于k时直接存放在result容器中
                result.push_back(input[i]);
            else
            {
                if (change)
                {
                    // 对result容器中k个元素进行大顶堆排序
                	for (int j = k/2; j >= 0; j--)
                    	HeadAdjust(result, j, k);  
                	// 将无序的大顶堆进行有序排列,将堆顶与最后一个元素互换，然后对前k-1个元素进行大顶堆排序
                	for (int j = k -1; j > 0; j--)
                	{
                    	swap(result[0],result[j]);
                    	HeadAdjust(result, 0, j);
                	}
                    change = false;
                }
                
                if (result[k-1] > input[i])
                {
                    result[k-1] = input[i];
                    change = true;
                }
                    
            }
        }
        return result;
    }
};

参考博文链接：https://cuijiahua.com/blog/2017/12/basis_29.html

https://www.icourse163.org/learn/XMU-1206002801?tid=1450366458#/learn/content?type=detail&id=1214739254&sm=1