剑指offer 最小的k个数

系统管理员 2024-04-17 14:46 7阅读 0赞

# [剑指offer题型分类及各题的解题思路与代码（<---点我跳转  ^ - ^）][offer_---_ _ -] #

## 1、题目描述 ##

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

## 2、初始结构定义如下 ##

class Solution 
    {
    public:
        vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {}
    };

## 3、思路及C++实现代码 ##

## ##

### 方法一：利用vector的sort直接排序 ###

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

### 方法二：红黑树multiset(有点难理解~) ###

来自：[https://www.nowcoder.com/questionTerminal/6a296eb82cf844ca8539b57c23e6e9bf?f=discussion][https_www.nowcoder.com_questionTerminal_6a296eb82cf844ca8539b57c23e6e9bf_f_discussion]

class Solution 
    {
    public:
        vector<int> GetLeastNumbers_Solution(vector<int> input, int k) 
        {
            if(input.empty() || k > input.size())
                return vector<int>();
            //仿函数中的greater<T>模板，从大到小排序
            multiset<int, greater<int>> res;
            vector<int>::iterator it = input.begin();
            for(; it != input.end(); it++)
            {
                //将前k个元素插入集合
                if(res.size() < k)
                    res.insert(*it);
                else
                {
                    //第一个元素是最大值
                    multiset<int, greater<int>>::iterator tmp = res.begin();
                    //如果后续元素<第一个元素，删除第一个，加入当前元素
                    if(*it < *(res.begin()))
                    {
                        res.erase(tmp);
                        res.insert(*it);
                    }
                }
            }
            return vector<int>(res.begin(), res.end());
        }
    };

[offer_---_ _ -]: https://blog.csdn.net/qq_26079093/article/details/96605538
[https_www.nowcoder.com_questionTerminal_6a296eb82cf844ca8539b57c23e6e9bf_f_discussion]: https://www.nowcoder.com/questionTerminal/6a296eb82cf844ca8539b57c23e6e9bf?f=discussion