中位数贪心

对一组数，所有数到某一数字x的距离最短，x为这组数的中位数

证明

按升序排序数组，得到$[a_0, ..., a_{n-1}]$
想考虑最外层两个数$a_0$和$a_{n-1}$，当x位于这两个数外侧时，总是可以将x向两数靠近的方向移动，此时距离之和会减少；当x位于两数之间时，距离之和总为恒定的$a_{n-1}-a_0$
继续考虑$a_1$和$a_{n-2}$情况相同
最终x应当取数组的中位数，当n为奇数时可取唯一中位数，当n为偶数时可任取一个

例题

给你一个长度为 n 的整数数组 nums ，返回使所有数组元素相等需要的最小操作数。

在一次操作中，你可以使数组中的一个元素加 1 或者减 1 。

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

class Solution {
 public:
  int minMoves2(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    int mid = nums[nums.size() / 2];
    int res = 0;
    for (int n : nums) {
      res += abs(n - mid);
    }
    return res;
  }
};

参考

https://leetcode.cn/problems/5TxKeK/solutions/2627350/zhuan-huan-zhong-wei-shu-tan-xin-dui-din-7r9b

中位数贪心

例题​

参考​

例题

参考