文章目录
原题题目
代码实现(首刷自解 快排)
class Solution {
public:
int partition(vector<int>& arr,int left,int right)
{
swap(arr[(left + right) / 2],arr[left]);
int low = arr[left],l = left,r = right + 1,size = arr.size();
while(l < r)
{
while(l < right && arr[++l] <= low);
while(r > left && arr[--r] >= low);
if(l >= r) break;
swap(arr[l],arr[r]);
}
swap(arr[left],arr[r]);
return r;
}
void quick_sort(vector<int>& arr,int left,int right,int k)
{
if(left >= right) return;
int mid = partition(arr,left,right);
if(mid == k) return;
quick_sort(arr,left,mid-1,k);
quick_sort(arr,mid+1,right,k);
}
vector<int> getLeastNumbers(vector<int>& arr, int k) {
quick_sort(arr,0,arr.size()-1,k);
return vector<int>(arr.begin(),arr.begin() + k);
}
};