写点什么

【LeetCode】减小和重新排列数组后的最大元素 Java 题解

用户头像
HQ数字卡
关注
发布于: 2 小时前

题目描述

给你一个正整数数组 arr 。请你对 arr 执行一些操作(也可以不进行任何操作),使得数组满足以下条件:


arr 中 第一个 元素必须为 1 。任意相邻两个元素的差的绝对值 小于等于 1 ,也就是说,对于任意的 1 <= i < arr.length (数组下标从 0 开始),都满足 abs(arr[i] - arr[i - 1]) <= 1 。abs(x) 为 x 的绝对值。你可以执行以下 2 种操作任意次:


减小 arr 中任意元素的值,使其变为一个 更小的正整数 。重新排列 arr 中的元素,你可以以任意顺序重新排列。请你返回执行以上操作后,在满足前文所述的条件下,arr 中可能的 最大值 。


示例 1:
输入:arr = [2,2,1,2,1]输出:2解释:我们可以重新排列 arr 得到 [1,2,2,2,1] ,该数组满足所有条件。arr 中最大元素为 2 。
来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/maximum-element-after-decreasing-and-rearranging著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
复制代码

思路分析

  • 今天的题目描述比较长,需要认真分析,一句话理解是将数组排序之后,满足,arr[i]= 1, abs(arr[i] - arr[i - 1]) <= 1 中,所有数组元素的最大值。

  • 根据上述条件,所有数组元素的最小值为 0。在迭代过程中,使用相邻元素的 abs 值 -1 即可。

代码

    public int maximumElementAfterDecrementingAndRearranging(int[] arr) {        Arrays.sort(arr);        if (arr[0] != 1) {            arr[0] = 1;        }
int maxNum = 1; int n = arr.length; for (int i = 1; i < n; i++) { int temp = Math.abs(arr[i] - arr[i - 1]); if ( temp > 1) { arr[i] -= (temp - 1); } maxNum = Math.max(maxNum, arr[i]); }
return maxNum; }
复制代码

总结

  • 上述代码的时间复杂度是 O(n), 空间复杂度是 O(1)

  • 坚持每日一题,加油!

发布于: 2 小时前阅读数: 2
用户头像

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

评论

发布
暂无评论
【LeetCode】减小和重新排列数组后的最大元素Java题解