题解 | #最小的K个数#

方法一 基于堆排序

构建小顶堆arr[0:n-1]后，重复k次：

将堆顶交换到堆末，即swap(arr[0], arr[n-1])，调整arr[0:n-2]，使其为小顶堆。

arr[n-1:n-k]即为所求

方法二 基于快排

对于arr[beg:end]每次递归调整后，基准元素arr[j]不小于前面的元素，不大于后面的元素

如果j >= k, 说明j后面的元素不可能是前k个最小元素，无需对j后的元素arr[j+1:end]进行递归排序，只需要对j前的元素arr[beg:j-1]进行递归排序。这是与快排的唯一区别，用于提高效率。

如果j < k, 说明j前的元素包含在前k个最小元素，除了对j前的元素进行递归排序外，还需要对j后面的元素进行递归排序。

两种方法都实现一下：

//基于快排
class Solution {
public:
	int adjust(vector<int> &a, int beg, int end)
	{
		int i = beg + 1, j = end;
		int base = a[beg];
		while (i <= j)
		{			
			while (a[i] <= base && i <= j)
			{
				i++;
			}
			while (a[j] >= base && j >= i)
			{
				j--;
			}
			
			if (i < j)
			{
				swap(a[i], a[j]);
				i++;
				j--;
			}			
		}
		
		//循环完后i和i之后的元素都比base大 ，
		//j和j之前的元素都比base小
		swap(a[beg], a[j]);
		
		return j;
	}
	
	void qSort(vector<int> &vec, int k, int beg, int end)
	{
		if (beg >= end)
		{
			return;
		}
		
		int loc = adjust(vec, beg, end);
		
		if (loc > k - 1)
		{
			qSort(vec, k, beg, loc - 1);
		}
		else
		{
			qSort(vec, k, beg, loc - 1);
			qSort(vec, k, loc + 1, end);
		}
	}
	
    vector<int> GetLeastNumbers_Solution(vector<int> vec, int k) {		
		if (vec.empty() || k > vec.size())
		{
			vector<int> ret;
			return ret;
		}
		
        qSort(vec, k, 0, vec.size() - 1);
		vector<int> r(vec.begin(), vec.begin() + k);
		return r;
    }
}; 

//基于堆排序
class Solution {
public:
	//当一个节点进行了调整后，子树可能不满足堆了，所以要递归调整子节点
	void adjust(vector<int> &vec, int i, int len)
	{
		int lChildIndex = i * 2 + 1;
		if (lChildIndex >= len)
		{
			return;
		}
		
		int rChildIndex = i * 2 + 2;
		
		if (rChildIndex >= len)
		{
			if (vec[lChildIndex] < vec[i])
			{
				swap(vec[lChildIndex], vec[i]);
			}
		}
		else
		{
			if (vec[lChildIndex] <= vec[rChildIndex] && vec[lChildIndex] < vec[i])
			{
				swap(vec[lChildIndex], vec[i]);	
				adjust(vec, lChildIndex, len);
			}
			
			if (vec[rChildIndex] < vec[lChildIndex] && vec[rChildIndex] < vec[i])
			{
				swap(vec[rChildIndex], vec[i]);
				adjust(vec, rChildIndex, len);
			}
		}
	}
	
	void buildMinTopHeap(vector<int> &vec)
	{
		for (int i = vec.size() / 2 - 1; i >= 0; --i)
		{
			adjust(vec, i, vec.size());
		}
	}
	
	void heapSort(vector<int> &vec, int k)
	{
		buildMinTopHeap(vec);
		int len = vec.size();
		for (int i = 0; i < k; ++i)
		{
			swap(vec[0], vec[len - 1]);
			adjust(vec, 0, --len);
		}
	}
	
    vector<int> GetLeastNumbers_Solution(vector<int> vec, int k) {		
		if (vec.empty() || k > vec.size())
		{
			vector<int> ret;
			return ret;
		}
		
		heapSort(vec, k);
		vector<int> r(vec.rbegin(), vec.rbegin() + k);
		return r;
    }
};