专栏首页眯眯眼猫头鹰的小树杈leetcode453. Minimum Moves to Equal Array Elements

leetcode453. Minimum Moves to Equal Array Elements

题目要求

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得到的结果就是这个数组的最小值。

代码如下:

    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;
    }

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 固定窗口和滑动窗口算法了解一下

    最近在参与一个识别热点数据的需求开发。其中涉及了限流算法相关的内容。所以这里记录一下自己了解的各种限流算法,以及各个限流算法的实现。

    眯眯眼的猫头鹰
  • leetcode462. Minimum Moves to Equal Array Elements II

    问最少需要多少次操作,能够将数组中所有元素的值修改为一样的(操作是指将数组中的元素加一或者减一)

    眯眯眼的猫头鹰
  • leetcode349. Intersection of Two Arrays

    思路一模仿了归并排序的merge部分。先将两个数组分别排序,排序完成之后再用两个指针分别比较两个数组的值。如果两个指针指向的值相同,则向结果集中添加该元素并且同...

    眯眯眼的猫头鹰
  • Spark SQL 快速入门系列(1) | Spark SQL 的简单介绍!

       Spark SQL 是 Spark 用于结构化数据(structured data)处理的 Spark 模块.

    不温卜火
  • NeurIPS 2018首日:阿里霸气演示全中文Demo,谷歌发布“找新娘”图片识别竞赛

    两年前的2016年,依然被称为NIPS大会的该活动有5,000名注册参与者。去年,参会者人数达到8,000。到了今年,首批2,000张门票在放出12分钟内即售罄...

    大数据文摘
  • IIC下挂多外设,SCLK频率高导致挂死疑问

    最近做IIC接口下挂多个外设,但是发现SCLK速率设置为400KHz时,系统运行一段时间就卡死,主要是OLED的影响,万用表测量SCL SDA电平为高;查了下I...

    Winter_world
  • esproc vs python 5

    题目介绍:loan 表存储着贷款信息,包括贷款 ID,贷款总额、按月分期数、年利率。数据如下:

    py3study
  • Cookie实现购物车功能

    晚上没宵夜
  • 从神经科学到计算机视觉:人类与计算机视觉五十年回顾

    【新智元导读】本文简单的介绍了神经网络近50年的发展历程,从1968年的Hubel和Wiesel开展的猫实验,一直到李飞飞教授等人的成果。从本质上讲解了人工神经...

    新智元
  • 细说java系列之反射

    反射机制允许在Java代码中获取被JVM加载的类信息,如:成员变量,方法,构造函数等。 在Java包java.lang.reflect下提供了获取类和对象反射...

    2Simple

扫码关注云+社区

领取腾讯云代金券