Problem Statement
Given an integer array nums with a size n, the goal is to calculate the minimum number of operations needed to make all elements of the array equal. Each operation consists of either increasing or decreasing any element in the array by one. The challenge lies in determining the most efficient series of operations to achieve uniformity across the array's values. Additionally, it's ensured that the solution will be within the range of a 32-bit integer.
Examples
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.length1 <= nums.length <= 105-109 <= nums[i] <= 109
Approach and Intuition
To derive the minimum number of moves to make all elements in the array equal, considering the following can be helpful:
Understanding Median:
The median of the array is the key to minimizing the total number of moves. The reason is straightforward: changes made towards the median are smaller compared to changes made towards the mean or any other statistic.Steps to Solution:
- Sort the Array: This helps in easily finding the median and simplifies calculation.
- Identify the Median: For an array with an odd number of elements, the median is the middle element. For an even number of elements, it can be any of the two middle values (though traditionally the lower middle is used).
- Calculate Moves: Determine the number of moves by calculating the absolute difference between each element and the median, then summing these differences.
Example Walkthrough:
Example 1 (
nums = [1,2,3]):- Sorting is
[1, 2, 3], median is2. - Moves: |1 - 2| + |2 - 2| + |3 - 2| = 1 + 0 + 1 = 2.
- Thus, 2 moves are required, aligning with the output.
- Sorting is
Example 2 (
nums = [1,10,2,9]):- Sorting is
[1, 2, 9, 10], median can be2or9(choosing2for fewer overall changes). - Moves: |1 - 2| + |2 - 2| + |9 - 2| + |10 - 2| = 1 + 0 + 7 + 8 = 16.
- This results in a total of 16 moves, matching the expected output.
- Sorting is
By understanding the significance of the median in this context, the approach becomes intuitive and computationally efficient, especially for large arrays within the constraints given.
Solutions
- Java
public class Algorithm {
public void exchange(int[] sequence, int idx1, int idx2) {
int temporary = sequence[idx1];
sequence[idx1] = sequence[idx2];
sequence[idx2] = temporary;
}
public int findPivotIndex(int[] sequence, int start, int end, int pivotVal) {
int partitionIndex;
for (partitionIndex = start; partitionIndex < end; partitionIndex++) {
if (sequence[partitionIndex] == pivotVal) {
break;
}
}
exchange(sequence, partitionIndex, end);
int pivot = sequence[end];
int destinationIndex = start;
for (partitionIndex = start; partitionIndex <= end; partitionIndex++) {
if (sequence[partitionIndex] < pivot) {
exchange(sequence, destinationIndex, partitionIndex);
destinationIndex++;
}
}
exchange(sequence, end, destinationIndex);
return destinationIndex;
}
int determineMedian(int array[], int from, int span) {
Arrays.sort(array, from, from + span);
return array[from + span / 2];
}
int selectKthSmallest(int array[], int left, int right, int k) {
if (k > 0 && k <= right - left + 1) {
int size = right - left + 1;
int i, median[] = new int[(size + 4) / 5];
for (i = 0; i < size / 5; i++) {
median[i] = determineMedian(array, left + i * 5, 5);
}
if (i * 5 < size) {
median[i] = determineMedian(array, left + i * 5, size % 5);
i++;
}
int medianOfMedians = (i == 1) ? median[i - 1] : selectKthSmallest(median, 0, i - 1, i / 2);
int pos = findPivotIndex(array, left, right, medianOfMedians);
if (pos - left == k - 1) {
return array[pos];
}
if (pos - left > k - 1) {
return selectKthSmallest(array, left, pos - 1, k);
}
return selectKthSmallest(array, pos + 1, right, k - pos + left - 1);
}
return Integer.MAX_VALUE;
}
public int minimizeMoves2(int[] elements) {
int total = 0;
int med = selectKthSmallest(elements, 0, elements.length - 1, elements.length / 2 + 1);
for (int element : elements) {
total += Math.abs(med - element);
}
return total;
}
}
This Java implementation tackles the problem of reducing an array of integers to all equal elements with the minimum number of moves by making all elements equal to the median. The medians' special property minimizes the sum of absolute differences compared to any other number.
- The
exchangemethod swaps two elements in an array, using a temporary variable to hold one of the values during the swap. - The
findPivotIndexmethod adjusts the array around a pivot value (chosen as the median of medians) such that elements less than the pivot are on the left, and elements greater are on the right, then returns the new position of the pivot. determineMediandetermines the median of a portion of the array by sorting the sub-array and selecting the middle element.selectKthSmallestuses a variant of the Quickselect algorithm to find the k-th smallest element efficiently. It divides the array into groups, finds the median of each group, then recursively finds the median of these medians.minimizeMoves2calculates the total number of moves needed to make all elements equal by selecting the median as the target and summing the absolute differences between each array element and this median.
This method leverages sorting, partitioning, and efficient median-finding techniques to solve the problem optimally, ensuring an efficient calculation of the required moves for large arrays. The recursive approach in selecting the k-th smallest element allows the algorithm to avoid full sorting, thus optimizing performance.
No comments yet.