文档章节

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

叶枫啦啦
 叶枫啦啦
发布于 2017/06/27 16:58
字数 304
阅读 5
收藏 0
点赞 0
评论 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;
    }
}

© 著作权归作者所有

共有 人打赏支持
叶枫啦啦
粉丝 6
博文 552
码字总数 295719
作品 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
Go语言规范(类型与值的属性)

原文:http://golang.org/doc/gospec.html Properties of types and values 类型和值的属性 Two types are either identical or different, and they are either compatible or incompatibl......

曾赛
2010/04/27
0
0
[LeetCode] Target Sum 目标和

You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now you have 2 symbols and . For each integer, you should choose one from and as its new symbol.......

机器的心脏
2017/12/10
0
0
mongodb CRUD操作 -Select

二、查询文档 方法: db.collection.find() Additional Methods db.collection.findOne In aggregation pipeline, the $match pipeline stage provides access to MongoDB queries. db.inve......

会说话的鱼
04/15
0
0
JavaScript30秒, 从入门到放弃

有意思 最近很火的上的库,特别有意思,代码也很优雅。 能学es6 自己翻译,能学英语 代码很美,很优雅,美即正义 函数式表达,享受 arrayGcd Calculates the greatest common denominator (g...

supermao
2017/12/25
0
0
Codeforces 960C - Subsequence Counting 【思维+构造】

C. Subsequence Counting time limit per test 1second memory limit per test 256megabytes Pikachu had an array with him. He wrotedown all the non-empty subsequences of the array on......

my_sunshine26
04/08
0
0
合并排序数组

原题   Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.   Note:   You may assume that nums1 has enough space (size that is grea......

一贱书生
2016/12/19
2
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

自定义OkHttp的UA

背景 上次的问题很明显 由于我们的ua清一色OkHttp导致快速定位到内部应用。 既然如此我们是否考虑可以在UA上做点手脚。 自定义我们的UA呢??? 分析 首先UA在 均为okhttp/3.2.0 大概率是由于...

Mr_Qi
21分钟前
0
0
【scikit-learn】01:使用案例对sklearn库进行简单介绍

sklearn学习笔记:Quick Start 源地址:http://scikit-learn.org/stable/tutorial/basic/tutorial.html # -*-coding:utf-8-*-''' Author:kevinelstri Datetime:2017.2.16'''......

wangxuwei
25分钟前
0
0
Linux Kernel 4.16 系列停止维护,用户应升级至 4.17

知名 Linux 内核维护人员兼开发人员 Greg Kroah-Hartman 近日在发布 4.16.18 版本的同时,宣布这是 4.16 系列的最后一个维护版本,强烈建议用户立即升级至 4.17 系列。 Linux 4.16 于 2018 年...

问题终结者
26分钟前
0
0
Apache配置时.htaccess失效不起作用的原因分析

.htaccess 失效的原因 1. 重写规则有问题,检查自己的重写规则 2.Apache配置问题,配置中没有配置启用 rewrite a2enmod rewrite 3.网站配置文件没有启用配置需要配置 000-default.conf <Dire...

TU-DESGIN
46分钟前
1
0
两个求最大公约数C/C++算法实现

#include<stdio.h> #include<time.h> #include <iostream>using namespace std;//求最大公约数 LCD(Largest Common Division)//短除法 //m=8251, n=6105; int LCD_ShortDiv(int m, ......

失落的艺术
52分钟前
1
0
QueryPerformanceCounter

windows的Sleep函数,睡眠线程指定毫秒数,可以用来做毫秒延时。 对于微秒延时,没有一个现成的函数,但是可以通过 QueryPerformanceFrequency QueryPerformanceCounter 来间接实现。原理就是...

开飞色
今天
1
0
log4j2使用AsyncRoot不显示行号问题处理

<AsyncRoot level="info" includeLocation="true"> <AppenderRef ref="File"/></AsyncRoot><!--1.异步logger,还需要在pom.xml中添加disruptor的依赖。2.includeLocation结合异......

小翔
今天
3
0
安卓手机上 K 歌,声音延迟怎么解决?

这篇文章可以为你提供一个解决录音和播放同步问题的思路,而且解决了声音从手机传输到耳机上有延时的问题。 初识音频 在开始之前,我先简单介绍一下音频相关的基础知识,方便下文理解。 我们...

编辑部的故事
今天
2
0
使用token实现在有效期内APP自动登录功能

使用token实现在有效期内APP自动登录功能 http://sevennight.cc/2016/07/19/auto_login_impl.html

风云海滩
今天
2
0
Spring Boot集成RabbitMQ发送接收JSON

默认情况下RabbitMQ发送的消息是转换为字节码,这里介绍一下如何发送JSON数据。 ObjectMapper 最简单发送JSON数据的方式是把对象使用ObjectMapper等JSON工具类把对象转换为JSON格式,然后发送...

小致dad
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部