A.每日一题：1846. 减小和重新排列数组后的最大元素-北京尧图网络

题目链接1846. 减小和重新排列数组后的最大元素中等算法原理解法一贪心直接排序7ms击败82.31%时间复杂度O(n logn)贪心思路很简单将整个数组从小到大升序排序由于所有数都≥1因此将第一个元素设置为1往后依次遍历如果发现 arr[i]-arr[i-1]1就将 arr[i] 设置为 arr[i-1]1最终的 arr[n-1] 即为答案解法二贪心计数排序3ms击败98.01%时间复杂度O(N)对于最终的数组从左往右看第一个数是1在持续递增的情况下最后一个数最多为 n这就意味着原数组 arr 中所有n 的数都要减小到≤ n因此 ≥ n 的数都可以视作 n这样我们就确定好了上限可以在 1~n 之间使用计数排序进行计算了~~遍历数组统计它们的个数数组记 cnt[x]为 arr 中 x 的个数和解法一相同从左往右遍历一遍假设现在遍历完 ≤ 4 的数得到的最大值为2那么我们继续遍历的过程中①如果 cnt[5]2新的最大值是多少第一个5减小为3第二个5减小为4这样就能续上了最大值为4②如果 cnt[5]4新的最大值是多少第一个5减小为3第二个5减小为4第三个5不变第四个5不变最大值为5因此当遍历到 cnt[x]之前得到的最大值为 mx那么到 cnt[x]的时候我们可以将 mx 增大至 mxcnt[x]但这个数不能超过 x因此计算式子为 mxmin(mxcnt[x],x)Java代码class Solution { //1846. 减小和重新排列数组后的最大元素 //解法一贪心直接排序 public int maximumElementAfterDecrementingAndRearranging(int[] arr) { int narr.length; Arrays.sort(arr); arr[0]1; for(int i1;in;i) if(arr[i]-arr[i-1]1) arr[i]arr[i-1]1; return arr[n-1]; } }class Solution { //1846. 减小和重新排列数组后的最大元素 //解法二贪心计数排序 public int maximumElementAfterDecrementingAndRearranging(int[] arr) { int narr.length; int[] cntnew int[n1]; for(int x:arr) cnt[Math.min(n,x)]; int mx0; for(int x1;xn;x) mxMath.min(mxcnt[x],x); return mx; } }

A.每日一题：1846. 减小和重新排列数组后的最大元素

相关推荐

AI代码生成变便宜了说“好“的成本反而更贵

TV Bro电视浏览器终极指南：用遥控器轻松实现大屏上网体验

游戏测试为什么这么难

更多资讯

Backstage 后端模块（Backend Modules）深度解析：用扩展点扩展插件的能力边界

终极RPA-Python自动化指南：如何用Python快速解放你的双手

Apache Doris数据接口：Stream Load五分钟跑通与多语言集成

Transformers 中的 CPM 中文预训练语言模型：GPT-2 架构与 Jieba-RS + SentencePiece 分词器解析

Umi-OCR：免费开源的离线OCR软件，截图、批量图片与PDF一键文字识别

电动车租赁会员管理系统：C#三层架构设计与实现

今日更新

Linux 内核 ARM 虚拟内存布局全解析：从 4GB 地址空间划分到源码级验证

AIGC降重工具测评与教育应用指南

数据容灾核心指标与实战方案解析

本周精选

超人会飞不算本事：系统稳定依赖清晰规则与边界设计

超人VS蜘蛛侠：拆解超级IP的影响力与传播方法论

基于CNN的调制信号识别：MATLAB实现时频图分类实战

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

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