题解 | #最小的K个数#
最小的K个数
http://www.nowcoder.com/practice/6a296eb82cf844ca8539b57c23e6e9bf
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;
}
};
