题解 | #最小的K个数#

class Solution {
public:
	int partion(vector<int>& input, int beg, int end)
	{
		int key = input[beg];
		while (beg < end)
		{
			while (beg < end && input[end] >= key)end--;
			input[beg] = input[end];
			while (beg < end && input[beg] <= key)beg++;
			input[end] = input[beg];
		}
		input[beg] = key;
		return beg;
	}
	vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
		if (input.size() == 0 || input.size() < k || k <= 0)
            return {};
		int pos = partion(input, 0, input.size() - 1);
//注意是k-1
		while (pos != k - 1)
		{
			if (pos > k - 1)
				pos = partion(input, 0, pos - 1);
			else
				pos = partion(input, pos + 1, input.size() - 1);
		}
		vector<int> res(input.begin(), input.begin() + k);
		return res;
	}
};