难度 中等

题目 Leetcode:

1846.Maximum Element After Decreasing and Rearranging

　　

　　You are given an array of positive integers arr. Perform some operations (possibly none) on arr so that it satisfies these conditions:

• 　　The value of the first element in arr must be 1.
• 　　The absolute difference between any 2 adjacent elements must be less than or equal to 1.In other words, abs(arr[i] - arr[i - 1]) <= 1 for each i where 1 <= i < arr.length (0-indexed). abs(x) is the absolute value of x.

　　There are 2 types of operations that you can perform any number of times:　　

• 　　Decrease the value of any element of arr to a smaller positive integer.
• 　　Rearrange the elements of arr to be in any order.

　　Return the maximum possible value of an element in arr after performing the operations to satisfy the conditions.

　　1 <= arr.length <= 10^5

　　1 <= arr[i] <=10^9

 

题目解析

本题题目来自力扣题库1846，是一道中等难度的题目。

本题同IQ test的题意很类似，但做法完全不同，难度也提升了一个等级

大概翻译就是给了一个正整数的数组arr，我们需要进行若干次操作使得数组满足两个条件，一个是arr[0]=1，另一个是每两个相邻的元素相减绝对值<=1，操作只有两种，一种是交换顺序，另一种是使其中一个元素减少到一个值，求数组合法后数组中最大的数字。

本题的思路很简单，先将数组从小到大排序，然后遍历数组，判断当前数字和上一个数字+1谁大谁小，小的那一个作为当前数字的值，继续遍历，这样的时间复杂度为O(n)，而事实上我们可以进行一些优化。

我们很轻易的就能发现，事实上最极端的情况数组会转换成[1,2,3,……,length]，这也意味着所有大于length的数组元素都会减到一定的值，我们这里将这些个数都看作length，用另外一个数组ans来记录每个小于等于length的数字出现了多少次（也包括看作length的元素），接着再对新的数组从0开始遍历，如果当前数字没出现过（ans[i]==0)，就说明需要一个被看作length的数字，操作为cnt++,如果出现过，我们就把当前多余的ans[i]也用来填补前面缺少的部分（指ans[i]==0的地方），这里因为我们会优先填补较小的部分，因此剩余缺失元素必然是 [n-miss+1,n]这一范围内的miss 个数，因此答案为 n-miss。

解析完毕，以下为参考代码

 1 class Solution {
 2 public:
 3     int maximumElementAfterDecrementingAndRearranging(vector<int>& arr) {
 4         int length=arr.size();
 5         int cnt=0;
 6         vector<int>ans(length+1);
 7         for(int i:arr)ans[min(i,length)]++;
 8         for(int i=1;i<=length;i++)
 9         {
10             if(ans[i]==0)cnt++;
11             else cnt-=min(ans[i]-1,cnt);
12         }
13        return length-cnt;
14     }
15 };