最小的K个数

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

来自牛客 剑指offer

题目描述

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

vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
    if (k < 1 || input.size() < k)
        return vector<int>();
        
    auto begin = input.begin();
    auto end = input.end() - 1;
    auto flag = *end;
    vector<int> result;
    while (true)
    {
        auto current = partition(begin, end,
                                    [flag](auto n) { return n < flag; });
        swap(*current, *end);
        if (current < input.begin() + k - 1)
        {
            begin = current + 1;
            flag = *end;
        }
        else if (current > input.begin() + k - 1)
        {
            end = current - 1;
            flag = *end;
        }
        else
        {
            result.assign(input.begin(), input.begin() + k);
            return result;
        }
    }
}