难度: 中等 | 标签: 数学 数组

1. 题目描述

https://leetcode.cn/problems/minimum-moves-to-equal-array-elements-ii/
给你一个长度为 n 的整数数组 nums ，返回使所有数组元素相等需要的最少移动数。
在一步操作中，你可以使数组中的一个元素加 1 或者减 1 。

示例 1：
输入：nums = [1,2,3]
输出：2
解释：
只需要两步操作（每步操作指南使一个元素加 1 或减 1）：
[1,2,3] => [2,2,3] => [2,2,2]
示例 2：
输入：nums = [1,10,2,9]
输出：16

提示：

  • n == nums.length
  • 1 <= nums.length <= 105
  • -109 <= nums[i] <= 109

通过次数: 19,491 | 提交次数: 31,623

2. 题解

2022-05-19 AC, 都变为**中位数**为最优解
一开始直觉是都变为**平均数**, 但是当数组里有2个较大的值时[1,800,810], 那么去把1加到800 肯定要比 两个800多的变成537要好

  1. <?php
  2. /**
  3.  * Created by PhpStorm
  4.  * User: jtahstu
  5.  * Time: 2022/5/19 2:16
  6.  * Des: 462. 最少移动次数使数组元素相等 II
  7.  *      https://leetcode.cn/problems/minimum-moves-to-equal-array-elements-ii/
  8.  *      给你一个长度为 n 的整数数组 nums ，返回使所有数组元素相等需要的最少移动数。在一步操作中，你可以使数组中的一个元素加 1 或者减 1 。
  9.  */
  11. class Solution
  12. {
  14.     /**
  15.      * @param Integer[] $nums
  16.      * @return Integer
  17.      */
  18.     function minMoves2($nums)
  19.     {
  20.         $n = count($nums);
  21.         sort($nums);
  22.         $mid = $nums[$n >> 1];
  23.         $count = 0;
  24.         for ($i = 0; $i < $n; $i++) {
  25.             $count += abs($nums[$i] - $mid);
  26.         }
  27.         return $count;
  28.     }
  29. }
  31. /**
  32.  * 两边都加减到中位数是最优解
  33.  *
  34.  * 执行用时：24 ms, 在所有 PHP 提交中击败了100.00%的用户
  35.  * 内存消耗：19.9 MB, 在所有 PHP 提交中击败了100.00%的用户
  36.  * 通过测试用例：30 / 30
  37.  */