目录

1. 问题描述

2. 思路与算法

3. 代码实现

1. 问题描述

给你一个长度为 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 <= 10^5
• -10^9 <= nums[i] <= 10^9

2. 思路与算法

         等价于以下优化问题：

        求某一个数，使得整个数组到达该数的距离之和最小化，并求该距离之和。该数可能在原数组中也可能不在原数组中。

         假设已经找到了满足条件的。

        考虑将加一，会使得原本比大的数与的距离减一， 比小的数与的距离加一，而由于满足题设条件（即所有数到达它的距离之和最小），因此，原来比小的数的个数一定不小于 比大的数的个数。

        同理我们也可以得到， 原来比大的数的个数一定不小于 比小的数的个数。

        这说明必然是输入数组的中位数。

        最直观的做法是，将原数组排序。如果数组中元素个数为奇数，则正中间那个数即为中位数。如果数组中元素个数为偶数，则正中间的两个数即它们之间的（不在数组中的）整数均为满足本题要求的中位数。

        求出中位数后，遍历数组求各数与该中位数的距离之和即可。

3. 代码实现

class Solution:
    def minMoves2(self, nums: List[int]) -> int:
        nums.sort()
        medium = nums[len(nums)//2]
        return sum(( [abs(nums[k] - medium) for k in range(len(nums))] ))

        执行用时：44 ms, 在所有 Python3 提交中击败了62.08%的用户

        内存消耗：16.3 MB, 在所有 Python3 提交中击败了10.74%的用户

        几分钟解决问题，近几天被虐的体无完肤的渣渣重新捡回了一丢丢信心。

        官解还给出了另一种更快的方法。

        如上所述，首先要找出数组第小元素（从 0 开始计数）。求解数组第 k 小元素可以使用快速选择算法，具体算法推导可以参考「215. 数组中的第K个最大元素」。

        回到总目录：Leetcode每日一题总目录(动态更新。。。)