LeetCode Solutions
class Solution {
public:
int minMoves2(vector<int>& nums) {
const int n = nums.size();
nth_element(begin(nums), begin(nums) + n / 2, end(nums));
const int median = nums[n / 2];
return accumulate(begin(nums), end(nums), 0,
[&](int a, int b) { return a + abs(b - median); });
}
};
|
class Solution {
public int minMoves2(int[] nums) {
final int n = nums.length;
final int median = quickSelect(nums, 0, n - 1, (n + 1) / 2);
int ans = 0;
for (final int num : nums)
ans += Math.abs(num - median);
return ans;
}
private int quickSelect(int[] nums, int l, int r, int k) {
final int randIndex = new Random().nextInt(r - l + 1) + l;
swap(nums, randIndex, r);
final int pivot = nums[r];
int nextSwapped = l;
for (int i = l; i < r; ++i)
if (nums[i] <= pivot)
swap(nums, nextSwapped++, i);
swap(nums, nextSwapped, r);
final int count = nextSwapped - l + 1;
if (count == k)
return nums[nextSwapped];
if (count > k)
return quickSelect(nums, l, nextSwapped - 1, k);
return quickSelect(nums, nextSwapped + 1, r, k - count);
}
private void swap(int[] nums, int i, int j) {
final int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
|
import statistics
class Solution:
def minMoves2(self, nums: List[int]) -> int:
median = int(statistics.median(nums))
return sum(abs(num - median) for num in nums)
|
