专栏首页木又AI帮【leetcode刷题】T202-最少移动次数使数组元素相等 II

【leetcode刷题】T202-最少移动次数使数组元素相等 II

木又连续日更第68天(68/100)


木又的第202篇leetcode解题报告

数学类型第18篇解题报告

leetcode第462题:最少移动次数使数组元素相等 II

https://leetcode-cn.com/problems/minimum-moves-to-equal-array-elements-ii/


【题目】

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

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

【思路】

能想出这道题数学解法的人很牛逼!

很明显,我们应该找数组中间的某个数,然后计算移动步骤。

我们首先想到是平均数,不过好像不对,平均数很可能不是整数,需要处理;另外,好像结果并不是最小值。

其实,我们就是求解:min(abs(nums[0] - x) + abs(nums[1] - x) +… + abs(nums[n-1] - x))

那么,x应该是中位数。(我也不知道怎么解出来的【笑哭】)

我们可以从中位数推出最小值:

假设数组元素个数是奇数2n+1,那么大于中位数的有n个,这些数移动到中位数需要x步;小于中位数的有n个,这些数移动到中位数需要y步。那么总的移动步数为x+y步。如果不是中位数,比如中位数-1,那么大于中位数的,需要移动x+n步,小于中位数的,至少需要移动y-n步(有的数可能大于中位数-1),总的步数大于x+y步

假设数组元素个数是偶数,只要是两个中位数之间的数,都可以作为移动后的值。因为,如果小于中位数m1的数全部移动到m1,大于中位数m2(m2>=m1)的数全部移动到买m2,那么只要目标值在m1->m2之间,总的移动步数是确定的。

【代码】

python版本

class Solution(object):
    def minMoves2(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums.sort()
        target = nums[len(nums) // 2]
        return sum(map(lambda x: abs(x - target), nums))

C++版本

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

前一篇文章:T201-最小移动次数使数组元素相等

本文分享自微信公众号 - 木又AI帮(gh_eaa31cab4b91),作者:木又

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-11-24

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【leetcode刷题】T9-寻找旋转排序数组中的最小值

    今天分享leetcode第9篇文章,也是leetcode第153题—寻找旋转排序数组中的最小值,地址是:https://leetcode.com/problem...

    木又AI帮
  • 【leetcode刷题】20T18-搜索旋转排序数组

    https://leetcode-cn.com/problems/search-in-rotated-sorted-array/

    木又AI帮
  • 【leetcode刷题】20T10-三数之和

    给定一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?找出所有满足条件且不重复的三元组...

    木又AI帮
  • BAT面试算法进阶(1)-两个数求和

    Given an array of integers, return indices of the two numbers such that they add...

    CC老师
  • 【leetcode刷题】20T18-搜索旋转排序数组

    https://leetcode-cn.com/problems/search-in-rotated-sorted-array/

    木又AI帮
  • 停止、暂停和恢复python解释器

    经过前面的一系列铺垫,现在要迎来我们的终极成果了——在运行我们自定义的函数过程中,如果要停止、暂停和再恢复python解释器,应该如何操作呢?

    用户5908113
  • goland/webstorm/pycharm/phpstorm2019.1破解教程

    因为goland已经升级到2019.1.3,有少数部分的激活教程较老不能使用了,踩了不少坑.所以经过摸索汇总出新的激活方式.分享给大家.

    mojocn
  • linux中各种文件的颜色表示是什么意思?

    =============================================================================

    黑泽君
  • 为什么学人工智能首推Python 需要学习哪些知识

    为何学人工智能首推Python?需要学习哪些知识?简单地讲,人工智能就是图像处理,数据处理,语言处理等多技术融合,在我们生活中经常可见。比如,人脸扫码付款,就是...

    一墨编程学习
  • [开发]Python实现运维监控服务器硬

          今天通过使用Python开发针对服务器硬件运行状态的监控,简单了解下在虚拟环境中的运维监控的实现,算是给全面研究云计算开一个头。

    py3study

扫码关注云+社区

领取腾讯云代金券