C++ version of quickselect kth largest number:

class Solution {
public:
int minMoves2(vector<int>& nums) {
// O(n) sol by quickselect
int median=findKthLargest(nums,0,nums.size()-1,nums.size()/2+1);
int result=0;
for(int num:nums) result+=abs(num-median);
return result;
}
private:
int partition(vector<int>& nums, int l, int r) {
int pivot=nums[l+(r-l)/2];
while(l<r) {
while(l<r && nums[l]<pivot) l++;
while(l<r && nums[r]>pivot) r--;
if(nums[l]==nums[r]) l++;
else swap(nums[l],nums[r]);
}
return r;
}
int findKthLargest(vector<int>& nums, int l, int r, int k) {
int pos=partition(nums,l,r);
if(k-1==pos) return nums[pos];
else if(k-1<pos) return findKthLargest(nums,l,pos-1,k);
else return findKthLargest(nums,pos+1,r,k);
}
};