class Solution {
public:
int maximumElementAfterDecrementingAndRearranging(vector<int>& arr) {
}
};
1846. 减小和重新排列数组后的最大元素
给你一个正整数数组 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 。
示例 2：
输入：arr = [100,1,1000] 输出：3 解释： 一个可行的方案如下： 1. 重新排列arr得到[1,100,1000] 。2. 将第二个元素减小为 2 。 3. 将第三个元素减小为 3 。 现在arr = [1,2,3] ，满足所有条件。arr 中最大元素为 3 。
示例 3：
输入：arr = [1,2,3,4,5] 输出：5 解释：数组已经满足所有条件，最大元素为 5 。
提示：
1 <= arr.length <= 1051 <= arr[i] <= 109原站题解
python3 解法, 执行用时: 136 ms, 内存消耗: 22.6 MB, 提交时间: 2022-11-29 11:06:52
class Solution:
def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:
n = len(arr)
cnt = [0] * (n+1)
for v in arr:
cnt[min(v, n)] += 1
miss = 0 # 记录缺失数据
for c in cnt[1:]:
if c == 0:
miss += 1
else:
miss = miss - min(c-1, miss)
return n - miss
javascript 解法, 执行用时: 80 ms, 内存消耗: 54 MB, 提交时间: 2022-11-29 10:58:16
/**
* @param {number[]} arr
* @return {number}
*/
var maximumElementAfterDecrementingAndRearranging = function(arr) {
const n = arr.length;
const cnt = new Array(n + 1).fill(0);
for (const v of arr) {
++cnt[Math.min(v, n)];
}
let miss = 0;
for (let i = 1; i <= n; ++i) {
if (cnt[i] == 0) {
++miss;
} else {
miss -= Math.min(cnt[i] - 1, miss); // miss 不会小于 0，故至多减去 miss 个元素
}
}
return n - miss;
};
javascript 解法, 执行用时: 84 ms, 内存消耗: 50.6 MB, 提交时间: 2022-11-29 10:57:40
/**
* @param {number[]} arr
* @return {number}
*/
var maximumElementAfterDecrementingAndRearranging = function(arr) {
const n = arr.length;
arr.sort((a, b) => a - b);
arr[0] = 1;
for (let i = 1; i < n; ++i) {
arr[i] = Math.min(arr[i], arr[i - 1] + 1);
}
return arr[n - 1];
};
golang 解法, 执行用时: 124 ms, 内存消耗: 8.4 MB, 提交时间: 2022-11-29 10:57:15
func maximumElementAfterDecrementingAndRearranging(arr []int) int {
n := len(arr)
sort.Ints(arr)
arr[0] = 1
for i := 1; i < n; i++ {
arr[i] = min(arr[i], arr[i-1]+1)
}
return arr[n-1]
}
func min(a, b int) int {
if a < b {
return a
}
return b
}