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

Michael Amin 2021-05-04 12:07:42
leetcode reduce rearrange largest element


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://qdmana.com/2021/05/20210504120226065h.html

  1. JS: event flow
  2. Front end performance optimization: rearrangement and redrawing
  3. JS - deep and shallow copy
  4. JavaScript异步编程3——Promise的链式使用
  5. JavaScript asynchronous programming 3 -- chain use of promise
  6. Vue.js组件的使用
  7. The use of vue.js component
  8. How to judge whether a linked list has links
  9. Element UI custom theme configuration
  10. Text image parallax effect HTML + CSS + JS
  11. Spring的nohttp宣言:消灭http://
  12. Vue3 intermediate guide - composition API
  13. Analysis of URL
  14. These 10 widgets that every developer must know
  15. Spring's nohttp Manifesto: eliminate http://
  16. Learn more about JS prototypes
  17. Refer to await to JS to write an await error handling
  18. A short article will directly let you understand what the event loop mechanism is
  19. Vue3 uses mitt for component communication
  20. Characteristics and thinking of ES6 symbol
  21. Two way linked list: I'm no longer one-way driving
  22. Vue event and form processing
  23. Reactive TraderCloud实时外汇开源交易平台
  24. Reactive tradercloud real time foreign exchange open source trading platform
  25. Node.js REST API的10个最佳实践
  26. Ten best practices of node.js rest API
  27. Fiddler advanced usage
  28. Process from Vue template to render
  29. Promise up (asynchronous or synchronous)
  30. Principle and implementation of promise
  31. Vs code plug in sharing - run code
  32. Vue practical notes (1) introduction of Ant Design
  33. Vue actual combat notes (2) introduction of element plus
  34. Introduction to webpack
  35. Webpack construction process
  36. Vue notes
  37. The experience and lessons of moving from ruby megalith architecture to go microservice
  38. Using leancloud to add artitalk module to hexo blog
  39. Implementation of chrome request filtering extension
  40. Detailed introduction of beer import declaration elements and label quarantine [import knowledge]
  41. Gallop workflow engine design series 01 process element design
  42. VUE移动端音乐APP学习【十六】:播放器歌词显示开发
  43. Vue Mobile Music App learning [16]: player lyrics display development
  44. jquery cookie
  45. jquery cookie
  46. 体面编码之JavaScript
  47. JavaScript for decent coding
  48. React17 系统精讲 结合TS打造旅游电商平台
  49. React17 system combined with TS to build tourism e-commerce platform
  50. 2021-05-04 hot news
  51. HttpSession对象与Cooike的关系 以及 Cookie对象构造函数问题
  52. gRPC-Web:替代REST的gRPC的Javascript库包
  53. The relationship between httpsession object and cooike and the construction of cookie object
  54. Grpc Web: a JavaScript library package to replace rest grpc
  55. Building reactive rest API with Java - kalpa Senanayake
  56. PDF转HTML工具——用springboot包装pdf2htmlEX命令行工具
  57. Pdf to HTML tool -- Wrapping pdf2htmlex command line tool with springboot
  58. PDF转HTML工具——用springboot包装pdf2htmlEX命令行工具
  59. Pdf to HTML tool -- Wrapping pdf2htmlex command line tool with springboot
  60. Vue.js比jQuery更容易学习