# share my C++ solution, almost certain O(n) time complexity

• ``````class Solution {
public:
int PartitionAroundPivot(int left, int right, int pivot_idx, vector<int> &nums) {
int pivot_val = nums[pivot_idx];
int new_pivot_idx = left;
swap(nums[pivot_idx], nums[right]);
for (int i=left; i<right; i++) {
if (nums[i] < pivot_val)
swap(nums[i], nums[new_pivot_idx++]);
}
swap(nums[right], nums[new_pivot_idx]);
return new_pivot_idx;
}

int QuickSelect(vector<int> &nums, int k) {
int left = 0, right = nums.size()-1;
default_random_engine gen((random_device())());
while (left <= right) {
int pivot_idx = uniform_int_distribution<int>{left, right}(gen);
int new_pivot_idx = PartitionAroundPivot(left, right, pivot_idx, nums);
if (new_pivot_idx == k-1) {
return nums[k-1];
}
else if (new_pivot_idx > k-1) {
right = new_pivot_idx - 1;
}
else
left = new_pivot_idx + 1;
}
}

int minMoves2(vector<int>& nums) {
int ans = 0, median = QuickSelect(nums, (nums.size()+1)/2);
for (int i=0; i<nums.size(); i++)
ans += abs(nums[i]-median);
return ans;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.