462. Minimum Moves to Equal Array Elements II #

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.

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
109 <= nums[i] <= 10^9

Problem Summary #

Given a non-empty integer array, find the minimum number of moves required to make all array elements equal, where each move can increment or decrement one selected element by 1. You may assume that the length of the array is at most 10000.

Solution Ideas #

Abstracted as a mathematical problem, if we view each number in array a as a point on the horizontal axis, then according to the move count formula above, we need to find a point x on the horizontal axis such that the sum of the distances from these N points to x is minimized. There are 2 points worth considering: one is the median, and the other is the average. For a simple example, for the data set [1,0,0,8,6], the median is 1 and the average is 3. Calculating the number of moves separately, aligning to the median takes 14 moves, while aligning to the average takes 16 moves. Therefore, choose the median.
This problem can be proven mathematically: the number of moves when moving toward the average ≥ the number of moves when moving toward the median. The author will not provide the proof here; interested students can try proving it themselves.

Code #

package leetcode

import (
	"math"
	"sort"
)

func minMoves2(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	moves, mid := 0, len(nums)/2
	sort.Ints(nums)
	for i := range nums {
		if i == mid {
			continue
		}
		moves += int(math.Abs(float64(nums[mid] - nums[i])))
	}
	return moves
}