文档章节

使数组值相等的最小步数 Minimum Moves to Equal Array Elements

叶枫啦啦
 叶枫啦啦
发布于 2017/06/27 16:58
字数 304
阅读 5
收藏 0

问题:

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-1个值加1就是一个值减1,14ms

public class Solution {
    public int minMoves(int[] nums) {
        if (nums.length == 0) return 0;
        int min = nums[0];
        for (int n : nums) min = Math.min(min, n);
        int res = 0;
        for (int n : nums) res += n - min;
        return res;
    }
}
② 公式 sum(array)- n * min(array)。11ms

我们假设sum为移动前所有数组值之和,minNum是数组中的最小值,n是数组的长度,经过m次移动n-1个小于最大值的数,我们得到所有数组值相等为x.可以得到如下公式:
sum + m * (n - 1) = x * n
另外还有:x = minNum + m
最后,我们可以得到:sum - minNum * n = m

public class Solution {
    public int minMoves(int[] nums) {
        int min = Integer.MAX_VALUE;
        int sum = 0;
        for(int i = 0 ; i < nums.length ; i ++){
            min = Math.min(min, nums[i]);
            sum += nums[i];
        }
        return sum - nums.length * min;
    }
}

© 著作权归作者所有

共有 人打赏支持
叶枫啦啦
粉丝 10
博文 563
码字总数 334343
作品 0
海淀
最小移动次数 Minimum Moves to Equal Array Elements II

问题: Given a non-empty integer array, find the minimum number of moves required to make all array elements equal, where a move is incrementing a selected element by 1 or decre......

叶枫啦啦
01/06
0
0
CodeForces - 960B- Minimize the error(思维--优先队列)

You are given two arrays A and B, each of size n. The error, E, between these two arrays is defined . You have to perform exactly k1 operations on array A and exactly k2 operati......

akatsuki__itachi
04/13
0
0
决战Leetcode: easy part(51-96)

本博客是个人原创的针对leetcode上的problem的解法,所有solution都基本通过了leetcode的官方Judging,个别未通过的例外情况会在相应部分作特别说明。 欢迎互相交流! email: tomqianmaple@...

qq_32690999
02/09
0
0
Codeforces 864D - Make a Permutation! 【贪心】

D. Make a Permutation! time limit per test 2seconds memory limit per test 256megabytes Ivan has an array consisting of n elements. Each of the elements is aninteger from 1 to n.......

my_sunshine26
2017/09/25
0
0
[leetcode]Array

写在前面:解决数组问题有一些常见的思路,下面,在这里,对相应问题进行汇总。 一.定义新的索引 283 remove zeros(将数组中的零元素移到末尾) Given an array , write a function to mov...

u013250416
2017/11/13
0
0

没有更多内容

加载失败,请刷新页面

加载更多

【挑战剑指offer】系列03:逆序打印单链表

本系列的算法原题来自于“牛客网-剑指offer”,写这个板块,不仅仅是解决算法问题本身,更是手动提高难度、自行变式,思考更多的解决方案,以带给自己一些启发。 1. 【逆序打印单链表】原始题...

LinkedBear
10分钟前
1
0
Linux内存布局

今天这篇文章主要是我之前看Linux内核相关知识和博客Gustavo Duarte中。我主要是看了这篇博客,并且结合之前的知识,对内存管理的的理解又上升了一个档次。所以想通过这篇文章总结下。 我们先...

linuxprobe16
28分钟前
1
0
day94-20180921-英语流利阅读-待学习

记录死亡还是消费死者?自杀报道的媒体偏见 雪梨 2018-09-21 1.今日导读 自杀事件报道一直是新闻报道的重要部分,具有骇人听闻、吸引眼球的特点。可是在报道这些事件的时候,除了客观陈述事实...

飞鱼说编程
35分钟前
3
0
如何通过 J2Cache 实现分布式 session 存储

做 Java Web 开发的人多数都会需要使用到 session (会话),我们使用 session 来保存一些需要在两个不同的请求之间共享数据。一般 Java 的 Web 容器像 Tomcat、Resin、Jetty 等等,它们会在...

红薯
今天
3
0
C++ std::thread

C++11提供了std::thread类来表示一个多线程对象。 1,首先介绍一下std::this_thread命名空间: (1)std::this_thread::get_id():返回当前线程id (2)std::this_thread::yield():用户接口...

yepanl
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部