mirror of
https://github.com/halfrost/LeetCode-Go.git
synced 2025-07-07 01:44:56 +08:00
66 lines
1.9 KiB
Markdown
66 lines
1.9 KiB
Markdown
# [462. Minimum Moves to Equal Array Elements II](https://leetcode.com/problems/minimum-moves-to-equal-array-elements-ii/)
|
||
|
||
|
||
## 题目
|
||
|
||
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`
|
||
|
||
## 题目大意
|
||
|
||
给定一个非空整数数组，找到使所有数组元素相等所需的最小移动数，其中每次移动可将选定的一个元素加 1 或减 1。 您可以假设数组的长度最多为10000。
|
||
|
||
## 解题思路
|
||
|
||
- 这题抽象成数学问题是，如果我们把数组 a 中的每个数看成水平轴上的一个点，那么根据上面的移动次数公式，我们需要找到在水平轴上找到一个点 x，使得这 N 个点到 x 的距离之和最小。有 2 个点值得我们考虑，一个是中位数，另外一个是平均值。举个简单的例子，[1,0,0,8,6] 这组数据，中位数是 1，平均值是 3 。分别计算移动的步数，按照中位数对齐是 14，按照平均值对齐是 16 。所以选择中位数。
|
||
- 此题可以用数学证明，证明出，按照平均值移动的步数 ≥ 按照中位数移动的步数。具体证明笔者这里不证明了，感兴趣的同学可以自己证明试试。
|
||
|
||
## 代码
|
||
|
||
```go
|
||
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
|
||
}
|
||
``` |