0462. Minimum Moves to Equal Array Elements II =============================================== 题目信息 -------- :题号: 0462 :难度: Medium :主题: 整数数组、单元素加减一、共同目标值、最少移动 :原题: `LeetCode 0462 `_ :重点: 每次只修改一个元素 1 个单位、最终目标整数可自由选择、返回总操作次数的最小值 题目重述 -------- 给定整数数组 ``nums``。一次操作可以选择一个元素,将它增加 1 或减少 1。返回把所有数组元素变成同一个整数所需的最少操作次数。 ``nums.length`` 位于 ``[1, 10^5]``,每个元素位于 ``[-10^9, 10^9]``,题目保证答案适合 32 位有符号整数。最终共同值不要求原先存在于数组中;每个元素移动的次数等于它与目标值之差的绝对值。 自建示例 -------- 中间值作为共同目标: .. code-block:: text 输入:nums = [1, 4, 7] 输出:6 解释:把 1 增加到 4 需要 3 次,把 7 减少到 4 需要 3 次,总计 6 次;选择其他目标不会更少。 数组已经相等: .. code-block:: text 输入:nums = [5, 5] 输出:0 解释:所有元素已经相同,不需要任何操作。 绝对距离和在中位数处最小 ------------------------ 若把所有元素变成目标 ``t``,操作数为 ``sum |nums[i] - t|``。目标向右移动一个单位时,左侧元素的距离增加、右侧元素的距离减少;当左右元素数量平衡或从左侧转为右侧时,距离和达到最小,这正是排序数组的中位数位置。 排序后选取 ``nums[n/2]`` 作为目标即可。数组长度为偶数时,任意位于两个中间值之间的整数都能达到相同最小值,选右中位数不会影响答案。 C++ 实现 -------- .. code-block:: cpp class Solution { public: int minMoves2(std::vector& nums) { std::sort(nums.begin(), nums.end()); long long median = nums[nums.size() / 2]; long long moves = 0; for (int value : nums) { moves += std::llabs(static_cast(value) - median); } return static_cast(moves); } }; 代码分析 -------- 中位数使绝对距离和的左右斜率分别为负和正,任何其他目标都不能更小;偶数长度时中间区间上的目标等价。排序耗时 ``O(n log n)``,求和耗时 ``O(n)``,额外空间复杂度为 ``O(1)``(不计排序实现的栈)。