专栏首页Michael阿明学习之路LeetCode 462. 最少移动次数使数组元素相等 II(数学)

LeetCode 462. 最少移动次数使数组元素相等 II(数学)

1. 题目

给定一个非空整数数组,找到使所有数组元素相等所需的最小移动数,其中每次移动可将选定的一个元素加1或减1。 您可以假设数组的长度最多为10000。

例如:
输入:
[1,2,3]
输出:
2

说明:
只有两个动作是必要的(记得每一步仅可使其中一个元素加1或减1): 
[1,2,3]  =>  [2,2,3]  =>  [2,2,2]

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/minimum-moves-to-equal-array-elements-ii 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

2. 解题

  • 假设中间的数是x,那么一对数 a,b 的移动次数为 x-a + b-x = b-a 跟 x 无关,而且是最小的,当 x 不在 a,b 区间内,移动次数就会增加
  • 所以选取中间位置的数作为 x ,即可得到最小的移动次数
class Solution {
public:
    int minMoves2(vector<int>& nums) {
        sort(nums.begin(), nums.end());//先排序
        int ans = 0;
        for(int i = 0; i < nums.size(); ++i)
        	ans += abs(nums[i]-nums[nums.size()/2]);
        return ans;
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 697. 数组的度

    给定一个非空且只包含非负数的整数数组 nums 数组的度的定义是指数组里任一元素出现频数的最大值

    Michael阿明
  • LeetCode 80. 删除排序数组中的重复项 II

    给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素最多出现两次,返回移除后数组的新长度。

    Michael阿明
  • LeetCode 448. 找到所有数组中消失的数字

    给定一个范围在 1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组,数组中的元素一些出现了两次,另一些只出现一次。

    Michael阿明
  • LeetCode 697. 数组的度

    给定一个非空且只包含非负数的整数数组 nums 数组的度的定义是指数组里任一元素出现频数的最大值

    Michael阿明
  • LeetCode 80. 删除排序数组中的重复项 II

    给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素最多出现两次,返回移除后数组的新长度。

    Michael阿明
  • 每日算法系列【LeetCode 1250】检查「好数组」

    给你一个正整数数组 nums ,你需要从中任选一些子集,然后将子集中每一个数乘以一个任意整数,并求出他们的和。

    godweiyang
  • Leetcode 31 Next Permutation

    Implement next permutation, which rearranges numbers into the lexicographically...

    triplebee
  • 关关的刷题日记05 —— Leetcode 217. Contains Duplicate 方法1和方法2

    题目 Leetcode 217. Contains Duplicate Given an array of integers, find if the arra...

    WZEARW
  • LeetCode 448. 找到所有数组中消失的数字

    给定一个范围在 1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组,数组中的元素一些出现了两次,另一些只出现一次。

    Michael阿明
  • Array - 80. Remove Duplicates from Sorted Array II

    80、Remove Duplicates from Sorted Array II 相似题型: 26

    用户5705150

扫码关注云+社区

领取腾讯云代金券