前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >leetcode453. Minimum Moves to Equal Array Elements

leetcode453. Minimum Moves to Equal Array Elements

作者头像
眯眯眼的猫头鹰
发布2019-07-04 17:21:35
3280
发布2019-07-04 17:21:35
举报

题目要求

代码语言:javascript
复制
Given a non-empty integer array of size n, find the minimum number of moves required to make all array elements equal, where a move is incrementing n - 1 elements by 1.

Example:

Input:
[1,2,3]

Output:
3

Explanation:
Only three moves are needed (remember each move increments two elements):

[1,2,3]  =>  [2,3,3]  =>  [3,4,3]  =>  [4,4,4]

从一个长度为n非空整数数组中,找到能够使得数组中每个元素的值都相等的最少步数,一步是指选择对数组中的n-1个元素加一。比如将[1,2,3]这个数组达到均等的最小步数要求为3步,过程如下:

  1. [1,2,3]
  2. [2,3,3]
  3. [3,3,4]
  4. [4,4,4]

思路和代码

假设这个具有n个元素的数组中的最小值为min,这个数组所有元素的和为sum,使其达到均等的最小步数为move,均等的值为target,则可以得到公式sum + (n - 1) * move = target * n。其中,可以推导出target = min + move,即在每一步中都会对初始时最小的元素加一。对二者进行计算可以得出sum - move = min * n

至于为什么target = min + move,其实理由很简单。假如并不是每一步都会将最小的值加一,则这个值永远是最小值,它将永远无法达到最终的目标值。反过来想,这个题目等价于从目标值开始,每一步都会对某个值-1,直到回到初始数组,则每一次都被执行-1得到的结果就是这个数组的最小值。

代码如下:

代码语言:javascript
复制
    public int minMoves(int[] nums) {
        int min = Integer.MAX_VALUE;
        int sum = 0;
        for(int num : nums) {
            min = Math.min(min, num);
            sum += num;
        }
        
        return sum - min * nums.length;
    }
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目要求
  • 思路和代码
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档