LeetCode: 453 Minimum Moves to Equal Array Elements(easy)
2024-09-05 19:53:29
题目:
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,问最少需要多少次这样的操作才能让数组中所有的数字相等。那么我们想,为了快速的缩小差距,该选择哪些数字加1呢,不难看出每次需要给除了数组最大值的所有数字加1,这样能快速的到达平衡状态。但是这道题如果我们老老实实的每次找出最大值,然后给其他数字加1,再判断是否平衡,思路是正确,但是OJ不答应。
正确的解法相当的巧妙,需要换一个角度来看问题,其实给n-1个数字加1,效果等同于给那个未被选中的数字减1,比如数组[1,2,3], 给除去最大值的其他数字加1,变为[2,3,3],我们全体减1,并不影响数字间相对差异,变为[1,2,2],这个结果其实就是原始数组的最大值3自减1,那么问题也可能转化为,将所有数字都减小到最小值,这样难度就大大降低了,我们只要先找到最小值,然后累加每个数跟最小值之间的差值即可,参见代码如下:
class Solution {
public:
int minMoves(vector<int>& nums) {
int mn = INT_MAX, res = ;
for (int num : nums) mn = min(mn, num);
for (int num : nums) res += num - mn;
return res;
}
};
最新文章
- 解决“chrome提示adobe flash player 已经过期”的小问题
- keil uvision3 添加 STC单片机库
- 临时表之IF-ELSE
- JavaScript中var关键字的使用详解
- Django--models连表构建
- Java 集合深入理解(13):Stack 栈
- centos 卸载vsftpd方法
- Android源码解析--Quick Search in Settings
- LPC2378-Jlink 能下载程序,但是调试出现各种奇怪问题
- ios中从相册:相机中获取图片信息
- docker 系列 - Docker 安装和Hub Mirror地址设置
- 常见的SQL调优(SQL Tuning)Tips
- TortioseSVN切换账号教程
- 8.3 C++格式标识和操纵器
- PostgreSQL内部结构与源代码研究索引页
- [Shiro] - Shiro之SpringBoot中的使用
- mysqldump工具,通过--where选项,导出指定表中指定数据?
- Linq学习以及简单用法
- 近200篇机器学习&;深度学习资料分享(含各种文档,视频,源码等)(1)
- pt-variable-advisor(percona toolkit)
热门文章
- 算法(Algorithms)第4版 练习 1.5.24
- JSP<;jsp:forward>;与<;%@ include%>;
- R语言矩阵运算
- 十六 Django框架,信号
- php mysqli_get_server_version()函数
- stl_set.h
- hdu 3537 Daizhenyang&#39;s Coin(博弈-翻硬币游戏)
- 【LeetCode】014. Longest Common Prefix
- HLSL学习笔记(一):基础
- css 更换浏览器 默认图标