用快排的变体,快速选择算法,选择一个pivot,对数组进行划分,pivot左边小于vt[pivot], 右边则大于。 然后利用二分快速确定partion区间,直到收敛到k-1. 算法复杂度O(n),n为数组长度。 rand() class Solution { public: int partion(vector<int>& vt, int s, int e) { if (s >= e) return s; //随机选择一个哨兵,以便算法时间复杂度平均期望为O(n) int pivot = rand() % (e...