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; } }