网络异常，图片无法展示
|
「这是我参与2022首次更文挑战的第40天，活动详情查看：2022首次更文挑战」
给定一个非空整数数组，找到使所有数组元素相等所需的最小移动数，其中每次移动可将选定的一个元素加1或减1。 您可以假设数组的长度最多为10000。
例如:
输入: [1,2,3] 输出: 2 说明： 只有两个动作是必要的（记得每一步仅可使其中一个元素加1或减1）： [1,2,3] => [2,2,3] => [2,2,2] 复制代码
解题思路
首先我们思考一个问题，假如在村东头有一个超市，村西头有一个超市，村子中间有一个超市，现在要建立一个仓库，使得三个超市到仓库的总距离最小，仓库应该建立在哪里呢？
答案是村子中间。
其实本题和上述的例子是同样的道理，要想使得所有的元素相等，并且移动次数最小，就应该让所有的元素往中间移动，这样越靠近中间的元素的移动次数就会越少。
所以我们只需要获取输入数组的中位数，然后分别计算每个元素移动到中位数的步数，它们的和值就是总的最少移动次数。
代码实现
// 想要移动的次数最少，就应该所有的数字都往中间移动 // 所以移动的目标值应该是数组中所有数字的中位数 var minMoves2 = function (nums) { // 获取中位数 function getMid(arr) { // 对输入数组排序 arr.sort((a, b) => a - b) // 获取输入数组长度 const len = nums.length // 如果长度为奇数，则直接返回中间的元素 if (len % 2) return arr[len >> 1] // 否则需要获取数组中元素之和 let sum = 0 for (let i = 0; i < len; i++) sum += arr[i] // 然后获取在中间的两个数字 const num1 = arr[len >> 1] num2 = arr[(len >> 1) - 1] // 返回两个数字中最靠近元素之和的那一个 if (Math.abs(num1 - sum / 2) < Math.abs(num2 - sum / 2)) return num1 return num2 } const mid = getMid(nums) // 初始化结果值为 0 let ret = 0 // 遍历输入数组，计算与中位数的差值=> 就是每个元素移动到中位数的步数 for (let i = 0; i < nums.length; i++) { ret += Math.abs(nums[i] - mid) } // 返回结果值 return ret } 复制代码
至此我们就完成了 leetcode-462-最少移动次数使数组元素相等 II
如有任何问题或建议，欢迎留言讨论！👏🏻👏🏻👏🏻
