# Java randomized Quick Select solution, O(n) time.

• Note: The performance varies because of the random pivot selection.

``````public int minMoves2(int[] nums) {
int n = nums.length;
int moves = 0;
int medianPos = n/2;
int med = findKthSmallest(nums, medianPos, 0, n - 1);
for (int i = 0; i < nums.length; i++) {
moves += Math.abs(nums[i] - med);
}
return moves;
}
private int findKthSmallest(int [] nums, int k, int start, int end) {
if (start == end) return nums[start];
// Random pivot
Random rand = new Random();
int indexSwitch = rand.nextInt(end - start) + start;
swap(nums, end, indexSwitch);
// If you remove the 3 lines above, the code still works.
int pivot = nums[end];
int i = start;
int j = end - 1;
while (i < j) {
if (nums[i] < pivot) {
i++;
continue;
}
if (nums[j] >= pivot) {
j--;
continue;
}
swap(nums, i, j);
}
int pos = 0;
if (nums[j] >= pivot) {
swap(nums, j, end);
pos = j;
}
else {
swap(nums, j+1, end);
pos = j+1;
}
if (pos == k) return nums[pos];
else if (pos < k) return findKthSmallest(nums, k, pos + 1, end);
else return findKthSmallest(nums, k, start, pos - 1);
}
private void swap (int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}``````

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