当前位置:网站首页>Leetcode 1846. Reduce and rearrange the largest element of an array

Leetcode 1846. Reduce and rearrange the largest element of an array

2021-05-04 12:07:42 Michael Amin

1. subject

To give you one Positive integer Array arr . Please be right arr Do something ( You can also do nothing ), Make the array satisfy the following conditions :

  • arr in first The element must be 1 .
  • arbitrarily adjacent The absolute value of the difference between two elements Less than or equal to 1 , in other words , For arbitrary 1 <= i < arr.length ( Array index from 0 Start ), All satisfied with abs(arr[i] - arr[i - 1]) <= 1 .abs(x) by x The absolute value of .

You can do the following 2 Any number of operations :

  • Reduce arr The value of any element in , Make it a Smaller positive integers .
  • Rearrange arr The elements in , You can rearrange it in any order .

Please return to after performing the above operation , Under the conditions mentioned above ,arr It's possible that Maximum .

 Example  1:
 Input :arr = [2,2,1,2,1]
 Output :2
 explain :
 We can rearrange  arr  obtain  [1,2,2,2,1] , The array satisfies all the conditions .
arr  The largest element in this series is  2 .

 Example  2:
 Input :arr = [100,1,1000]
 Output :3
 explain :
 A feasible solution is as follows :
1.  Rearrange  arr  obtain  [1,100,1000] .
2.  Reduce the second element to  2 .
3.  Reduce the third element to  3 .
 Now?  arr = [1,2,3] , All conditions are met .
arr  The largest element in this series is  3 .

 Example  3:
 Input :arr = [1,2,3,4,5]
 Output :5
 explain : The array has met all the conditions , The largest element is  5 .
 
 Tips :
1 <= arr.length <= 10^5
1 <= arr[i] <= 10^9

source : Power button (LeetCode)
link :https://leetcode-cn.com/problems/maximum-element-after-decreasing-and-rearranging
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

2. Problem solving

  • According to the meaning of the title , Can sort , The first is 1, Then check in turn if the gap is greater than 1, Greater than 1 So the gap is 1, You can make the largest number the largest
class Solution {
    
public:
    int maximumElementAfterDecrementingAndRearranging(vector<int>& arr) {
    
        sort(arr.begin(), arr.end());
        arr[0] = 1;
        for(int i = 1; i < arr.size(); i++)
        {
    
            if(arr[i] - arr[i-1] > 1)
            {
    
                arr[i] = arr[i-1]+1;
            }
        }
        return arr.back();
    }
};

100 ms 50.1 MB C++


my CSDN Blog address https://michael.blog.csdn.net/

Long click or sweep code pay attention to my official account (Michael amin ), Come on together 、 Learn together !
Michael amin

版权声明
本文为[Michael Amin]所创,转载请带上原文链接,感谢
https://chowdera.com/2021/05/20210504120226065h.html

随机推荐