462. Minimum Moves to Equal Array Elements II

Question

LeetCode Problem

Given an integer array nums of size n , return the minimum number of moves required to make all array elements equal .
In one move, you can increment or decrement an element of the array by 1 .
Test cases are designed so that the answer will fit in a 32-bit integer.
Example 1:

Input: nums = [1,2,3] Output: 2 Explanation: Only two moves are needed (remember each move increments or decrements one element):
[ 1 ,2,3]  =>  [2,2, 3 ]  =>  [2,2,2]

Example 2:

Input: nums = [1,10,2,9] Output: 16

Constraints:

• n == nums.length
• 1 <= nums.length <= 10 5
• -10 9 <= nums[i] <= 10 9

Solutions

int partition (vector<int>& nums, int left, int right) {
	int pivot = nums[right];
	int i = left;
	for (int j = left, j < right; ++j) {
		if (nums[j] < pivot) {
			swap(nums[j], nums[i]);
			++i;
		}
	}
	swap(nums[i], nums[right]);
	return i;
}

int minMoves2(vector<int> &nums) {
	int n = static_cast<int>(nums.size());
	int k = n / 2;
	if (n <= 1) return n;
	int left = 0;
	int right = n - 1;
	int median = 0;
	while (left <= right) {
		int pivotIdx = partition(nums, left, right);
		if (k > pivotIdx) {
			left = pivotIdx + 1;
		} else if (k < pivotIdx) {
			right = pivotIdx - 1;
		} else {
			median = nums[k];
			break;
		}
	}
	long long moves = 0;
	for (int i = 0; i < n; ++i) {
		moves += 1LL * abs(nums[i] - pivotIdx);
	}
	
	return static_cast<int>(moves);
}