最小操作次数使数组元素相等 III【力扣LeetCode 每日一题】-北京尧图网络

3736. 最小操作次数使数组元素相等 III网页链接力扣LeetCode力扣LeetCode 每日一题完成每日打卡即可获得力扣积分。获得相应数量的积分能在【力扣商店】换取相应奖品助力每日有题做丰盈积分日益多题目描述给你一个整数数组nums。在一步操作中你可以将任意单个元素nums[i]的值增加 1。返回使数组中的所有元素都相等所需的最小总操作次数。输入描述一个整数数组nums。输出描述返回使数组中的所有元素都相等所需的最小总操作次数。示例示例 1输入nums [2,1,3]输出3解释使所有元素相等的操作如下将nums[0] 2增加 1变为 3。将nums[1] 1增加 1变为 2。将nums[1] 2增加 1变为 3。现在nums中的所有元素都等于 3。最小总操作次数为 3。示例 2输入nums [4,4,5]输出2解释使所有元素相等的操作如下将nums[0] 4增加 1变为 5。将nums[1] 4增加 1变为 5。现在nums中的所有元素都等于 5。最小总操作次数为 2。数据范围1 ≤ nums.length ≤ 100 1 \le \text{nums.length} \le 1001≤nums.length≤1001 ≤ nums [ i ] ≤ 100 1 \le \text{nums}[i] \le 1001≤nums[i]≤100解题思路本题是贪心目标值选择差值求和问题。每次操作只能将某个元素增加1不能减少。因此最终所有元素相等时目标值不可能小于数组当前的最大值否则最大值元素无法通过“增加”变成更小的值。所以最优目标值就是数组的最大值。1. 为什么目标值取最大值设数组最大值为M max ⁡ ( n u m s ) M\max(nums)Mmax(nums)由于只能对元素做加1操作若最终目标值小于M则当前最大元素M无法降低到目标值不可行若最终目标值大于M则所有元素都需要继续增加操作次数只会更多因此目标值取M时最优。2. 计算最少操作次数对于任意元素nums[i]要变成M需要增加M − n u m s [ i ] M - nums[i]M−nums[i]次。把所有元素的增加次数累加得到总操作次数∑ i 0 n − 1 ( M − n u m s [ i ] ) \sum_{i0}^{n-1} \bigl(M - nums[i]\bigr)i0∑n−1(M−nums[i])化简得n × M − ∑ i 0 n − 1 n u m s [ i ] n \times M - \sum_{i0}^{n-1} nums[i]n×M−i0∑n−1nums[i]代码正是按这个公式计算returnranges::max(a)*a.size()-reduce(a.begin(),a.end(),0);其中ranges::max(a)求数组最大值Ma.size()是数组长度nreduce(a.begin(), a.end(), 0)求数组元素总和。3. 示例验证对于nums [2,1,3]最大值M 3总和为2 1 3 6答案为3 × 3 − 6 3 3 \times 3 - 6 33×3−63与示例输出一致。对于nums [4,4,5]最大值M 5总和为4 4 5 13答案为3 × 5 − 13 2 3 \times 5 - 13 23×5−132与示例输出一致。4. 复杂度分析求最大值O ( n ) O(n)O(n)求数组总和O ( n ) O(n)O(n)总时间复杂度为O ( n ) O(n)O(n)只使用常数个额外变量空间复杂度为O ( 1 ) O(1)O(1)。总结由于操作只能增加元素最终相等值至少是数组最大值。取最大值作为目标值时总操作次数最小答案为n × max ⁡ ( n u m s ) − ∑ n u m s [ i ] n \times \max(nums) - \sum nums[i]n×max(nums)−∑nums[i]即最大值乘以数组长度再减去数组元素总和。整体只需一次线性扫描时间复杂度为O ( n ) O(n)O(n)。代码内容classSolution{public:intminMoves(vectorinta){returnranges::max(a)*a.size()-reduce(a.begin(),a.end(),0);}};

最小操作次数使数组元素相等 III【力扣LeetCode 每日一题】

相关推荐

asyncio.run() cannot be called from a running event loop：在 async 函数里该怎么改

Opus 4.8快速模式11月30日移除：两条迁移路径怎么选？

百炼Memory写入后搜不到？先查异步回执、规则和记忆类型

更多资讯

对话式诊断系统AMIE：从主诉到鉴别诊断的对话机制与评测体系

Linux USB设备管理：从识别到自动挂载的完整指南

Python租房数据分析系统：从爬虫到机器学习实战

Elasticsearch集群健康状态维护与性能优化实战

MySQL DQL数据查询语言全解析与优化实践

AI能力构建：6C模型驱动企业数字化转型

今日更新

多智能体协作系统架构设计与实践优化

大模型系统性入门实战指南：从原理到部署微调的全链路路线

鸿蒙文件系统沙箱机制解析与开发实践

本周精选

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？