当前位置: 首页 > news >正文

【LeetCode453.最小操作次数使数组元素相等】

题目链接

453. 最小操作次数使数组元素相等 - 力扣(LeetCode)

实现思路

借鉴了一下大佬的思路(453. 最小操作次数使数组元素相等 - 力扣(LeetCode)),然后基于自己原本的暴力解法来理解题目。

  • 最开始没看数据范围,直接模拟,每次对当前最小的n-1个数自增。
  • 但是,这里可以发现一个思想,就是每次一定会对最初最小的那个数做自增操作。
  • 现在,假设最终每个元素都变为t,操作次数为ans。那么(t*n - sum)/(n - 1) = ans.
  • 由于每次都会对最初最小的那个数mn进行自增操作,因此mn + ans = t.

代码实现

class Solution {
public:int minMoves(vector<int>& nums) {// 1.一个直觉的想法,贪心,每次肯定是对最小的n-1个数进行加1,但是这么做时间复杂度很高// int n = nums.size();// int cnt = 0;// while (true) {//     int flag = 1;//     for (int i = 1; i < n; i++) {//         if (nums[i] != nums[i - 1]) {//             flag = 0;//             break;//         }//     }//     if (flag) return cnt;//     sort(nums.begin(), nums.end());//     for (int i = 0; i < n - 1; i++) {//         nums[i]++;//     }//     cnt++;// }// return -1;// 2.数学法// 假设最终每个元素是t,操作次数是ans// 那么 (t * n - sum) / (n - 1) = ans// 并且,由上面贪心的想法,也可以知道,数组中最小的元素,每次都要参与+1操作// 那么 min + ans = t// 联立 ans = sum - min * nint sum = 0;int n = nums.size();int mn = nums[0];for (int i = 0; i < n; i++) {sum += nums[i];mn = min(mn, nums[i]);}return sum - mn * n;}
};

http://www.lryc.cn/news/585953.html

相关文章:

  • 代码训练LeetCode(45)旋转图像
  • 【Linux-云原生-笔记】Apache相关
  • 【Modern C++ Part9】Prefer-alias-declarations-to-typedefs
  • 内网穿透系列九:开源的网络穿透与组网工具 EasyTier,支持多种数据传输通道,去中心化,兼具高效与安全
  • Kafka Schema Registry:数据契约管理的利器
  • 对日开发 秀丸文本编辑器 添加文本变换模块
  • 聊一聊Spring框架接口测试常见场景有哪些?
  • 学习C++、QT---22(QT中QTextStream库读取文件、写入文件的讲解)
  • docker搭建 与镜像加速器
  • win10安装Rust Webassembly工具链(wasm-pack)报错。
  • C++中Lambda表达式 [ ] 的写法
  • AI 时代的分布式多模态数据处理实践:我的 ODPS 实践之旅、思考与展望
  • 深入解析 Stack 和 Queue:从原理到实战应用
  • 每日算法刷题Day46 7.12:leetcode前缀和3道题和差分2道题,用时1h30min
  • pgsql模板是什么?
  • Redis Geospatial 功能详解及多边形包含判断实现
  • 【JVM|类加载】第三天
  • 专业硬件检测工具 AIDA64 Extreme V7.70.7500 至尊版
  • 12. JVM的垃圾回收器
  • 1. 好的设计原则
  • Java应用全链路故障排查实战指南:从系统资源到JVM深度诊断
  • 钉钉小程序开发环境配置与前端开发指南
  • 【小沐杂货铺】基于Three.JS绘制汽车展示Car(WebGL、vue、react、autoshow、提供全部源代码)
  • 关于 验证码系统 详解
  • Ubuntu安装Jenkins
  • Java文件传输要点
  • 大数据在UI前端的应用深化研究:用户行为数据的时序模式挖掘
  • 前端内容-ES6
  • Java使用Langchai4j接入AI大模型的简单使用(一)
  • 【Linux网络】IP 协议详解:结构、地址与交付机制全面解析