躬行算法之最小的最大值
2021/9/30 9:11:08
本文主要是介绍躬行算法之最小的最大值,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
本文同时发布于我的个人网站 https://lomagicode.com/blog/algorithm-min-max-value/
最近看到这样一道面试题,求最小的最大值,觉得挺有意思,在这里分享下。
描述
给定一个数组 a,包含 n 个整数。再给定一个整数 k,可以给数据中任意整数加 1,总共可以加 k 次。加完 k 次之后,找出数组中的最大数,要求得到最小的最大数。
解析
乍一看,甚至题目都没读懂。啥,最大数,还最小?这道题最关键的也就是理解题目的含义,
有一种理解,我认为非常贴近生活,就是把数组 a 理解为若干个垃圾桶,这些垃圾桶中有数量不等的垃圾,而此时我们手里有 k 袋垃圾,可以任意投放。放在这个题目中,就是要找到合理的投放方式使得垃圾桶尽可能不要堆得太高,然后找到最满的桶中的垃圾数量。
这样一考虑,题目就变得非常简单了。
回到题目,首先计算出数组 a 中最大数为 max,尝试把所有小于 max 的数填平。若 k 值太小,无法填平,则最小的最大数即为 max;若 k 值够大,填平之后 k 还有剩余,则依次平铺,每一轮每个元素都加 1,直到 k 归零为止。
答案
根据以上分析,很容易写出以下答案:
private int findMinMaxValue(int[] array, int k) { int n = array.length, max = 0, sum = 0; for (int x : array) { max = Math.max(x, max); sum += x; } return k + sum <= n * max ? max : (k + sum + n - 1) / n; // (k+sum+n-1)/n 相当于 (k+sum)/n 向上取整 }
更多干货内容,敬请关注公众号:逻魔代码
这篇关于躬行算法之最小的最大值的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?