leetcode453. Minimum Moves to Equal Array Elements

栏目: 编程工具 · 发布时间: 5年前

内容简介:从一个长度为n非空整数数组中,找到能够使得数组中每个元素的值都相等的最少步数,一步是指选择对数组中的n-1个元素加一。比如将[1,2,3]这个数组达到均等的最小步数要求为3步,过程如下:假设这个具有n个元素的数组中的最小值为min,这个数组所有元素的和为sum,使其达到均等的最小步数为move,均等的值为target,则可以得到公式至于为什么

题目要求

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

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

数据结构

数据结构

殷人昆 / 清华大学 / 2007-6 / 39.00元

《数据结构》(第2版)“数据结构”是计算机专业的核心课程,是从事计算机软件开发和应用人员必备的专业基础。随着计算机的日益普及,“数据结构”课程也在不断地发展。《数据结构》(第2版)按照清华大学计算机系本科“数据结构”大纲的要求,从面向对象的概念、对象类设计的风格和数据结构的层次开始,从线性结构到非线性结构,从简单到复杂,深入地讨论了各种数据结构内在的逻辑关系及其在计算机中的实现方式和使用。此外,对......一起来看看 《数据结构》 这本书的介绍吧!

RGB转16进制工具
RGB转16进制工具

RGB HEX 互转工具

SHA 加密
SHA 加密

SHA 加密工具

html转js在线工具
html转js在线工具

html转js在线工具