解题思路：【c++】（1）排序：调用函数sort(arr.begin(),arr.end())得到从小到大的排列；再返回前k个数。 （2）大根堆（优先队列）：将前k个数先压入优先队列，再遍历数组剩下元素，若该元素比队列top元素（队列中最大值）小，将队列top元素取出，将其加入队列。 （3）快排思想：递归切分数组[left,right]数据，将左端数据作为切分点cur_num，双向遍历数组[left,right]元素，对调左向搜索大数与右向搜索小数（这里的大小数是与cur_num相比），最终实现[left,right]中比cur_num小的均在其左侧，比cur_num大的均在其右侧，返回值为cur_num下标pos。如果pos=k，则arr最小的k个数位于前k个位置，取出存入新的数组返回即可；若pos>k，说明第k个最小的数位于cur_num左侧，切分数组[left,pos-1]；若pos<k，说明第k个最小的值位于cur_num右侧，切分数组[pos+1,right]。函数入口[left,right]= [0, arr.size()-1]。
//c++ class Solution { public: vector<int> getLeastNumbers(vector<int>& arr, int k) { //solution 1:快速排序 // vector<int> nums(k,0); // sort(arr.begin(),arr.end()); // for(int i =0;i<k; ++i){ // nums[i] = arr[i]; // } // return nums; //solution 2:大根堆 // vector<int> nums(k,0); // priority_queue<int> que; // if(k==0) return nums; // for(int i=0; i<k;++i){ // que.push(arr[i]); // } // for(int i=k; i<arr.size(); ++i){ // if(arr[i]<que.top()){ // que.pop(); // que.push(arr[i]); // } // } // for (int i = 0; i<k;++i){ // nums[i] = que.top(); // que.pop(); // } // return nums; //solution3:快排变形，查找第k大元素 vector<int> nums; if(k==0 || arr.size()==0) return nums; quickSearch(arr, 0 ,arr.size()-1, k); for(int i = 0; i<k; ++i){ nums.push_back(arr[i]); } return nums; } void quickSearch(vector<int>& arr, int left, int right, int k) { if(left>=right) return; int pos = partition(arr, left, right); if (pos == k){ cout<<"find"<<endl; return; } else if(pos > k) quickSearch(arr, left, pos-1, k); else quickSearch(arr, pos+1, right, k); } int partition(vector<int>& arr, int left, int right){ int cur_num = arr[left]; int i = left+1, j=right; while(1){ while(i<right && arr[i]<=cur_num) ++i; while(j>left && arr[j]>=cur_num) --j; // cout<<"i:"<<i<<endl; // cout<<"j:"<<j<<endl; if(i>=j) break; int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } arr[left] = arr[j]; arr[j] = cur_num; //for(int i =0; i<arr.size();++i) cout<<arr[i]<<endl; return j; } }; # python3 class Solution: def getLeastNumbers(self, arr: List[int], k: int) -> List[int]: if not k or not arr: return [] nums = [] self.quickSearch(arr, 0 ,len(arr)-1, k) while(k): nums.append(arr[k-1]) k = k-1 return nums def quickSearch(self, arr, left, right, k): if left >= right: return pos = self.partition(arr, left, right) if pos == k: return elif pos>k: self.quickSearch(arr, left, pos-1, k) else: self.quickSearch(arr, pos+1, right, k) def partition(self, arr, left, right): cur = arr[left] i = left+1 j=right while(True): while i<right and arr[i]<=cur: i = i+1 while j>left and arr[j]>=cur: j=j-1 if i>=j: break temp = arr[i] arr[i] = arr[j] arr[j] = temp arr[left] = arr[j] arr[j] = cur return j