This is the fourth day of my participation in the August More Text Challenge.

The largest element after reducing and rearranging an array (item number 1846)

The title

I give you an array of positive integers, ARr. You can do something (or nothing) to the ARR to make the array satisfy the following conditions:

  • arr 中 The first oneThe element must be1 。
  • The absolute value of the difference between any two adjacent elementsLess than or equal to 1That is, for any1 <= i < arr.length （Array subscripts start at 0)abs(arr[i] - arr[i - 1]) <= 1 。abs(x) 为 xAbsolute value of.

You can perform the following two operations any time:

  • reducearrThe value of any element in theSmaller positive integers 。
  • Rearrange elements in arR, you can rearrange them in any order.

Return the maximum possible value in the ARR after performing the above operations under the conditions described above.

Example 1:

Input: arr = [2.2.1.2.1] output:2Explanation: We can rearrange arR to get [1.2.2.2.1], the array satisfies all criteria. The largest element in ARR is2 。
Copy the code

Example 2:

Input: arr = [100.1.1000] output:3Explanation: One possible solution is as follows:1.Rearrange arR to obtain [1.100.1000].2.Reduce the second element to zero2 。
3.Reduce the third element to zero3. Now arr = [1.2.3], all conditions are met. The largest element in ARR is3 。
Copy the code

Example 3:

Input: arr = [1.2.3.4.5] output:5Explanation: The array already satisfies all conditions, the maximum element is5 。
Copy the code

Tip:

  • 1 <= arr.length <= 105
  • 1 <= arr[i] <= 109

link

Leetcode-cn.com/problems/ma…

explain

This one? This one’s a punch line.

That’s pretty clear, but it’s important to note that the number starts at 1, not the first element in the sorted array.

The simple solution is to sort the array from smallest to largest.

Set the initial value to 1, which is the minimum.

After starting from the second element of the array traversal, if the current element is larger than the minimum value at least 1, it is proved that this number can be reduced to the point of is greater than the minimum 1, then give the minimum value since 1, if is as large as the minimum value, and also is the difference between less than 1, the minimum value can only be the minimum value, cannot be changed.

So you go all the way through the array, and the smallest value you get is the final answer.

The authorities offer another idea which is unique, I have to say, and put together with the answer

Your own answer (sort + traverse)

var maximumElementAfterDecrementingAndRearranging = function(arr) {
  arr.sort((a, b) = > a - b)
  var min = 1
  for (let i = 1; i < arr.length; i++) {
    min = arr[i] - min >= 1 ? min + 1 : arr[i]
  }
  return min
};
Copy the code

Specific logic and the above is the same, more surprising is that the time to beat 100% of the people, take off ~

A better way (counting sort + greedy)

This can be done in two steps:

  1. And they tell us that the numbers are increasing from 1 up tonThe ideal situation is to form an array like this, if the array has repeated less thannYou can’t get to that numbern, so the first step is to get all the arrays that match the criteria, thannLarge numbers are treated as suchnSo you know which numbers are missing and which numbers are duplicated.
  2. After you get the array above, you can start to operate, iterate through the result array above, and when you find a number that doesn’t appear, you givemissIf you increase the variable by 1, there’s an empty number! If there’s a number greater than 1, use itmissSubtract the numbers above 1. You have to be careful when you subtract becausemissIt can’t be negative, so you can only subtract at mostmiss.

After understanding the above two steps, you can look at the code 👇 :

var maximumElementAfterDecrementingAndRearranging = function(arr) {
  var n = arr.length
      cnt = new Array(n+ 1).fill(0)
      miss = 0
  for (const v of arr) {
    ++cnt[Math.min(v, n)]
  }
  for (let i = 1; i <= n; i++) {
    if (cnt[i] === 0) {
      miss++
    } else {
      miss -= Math.min(cnt[i] - 1, miss)
    }
  }
  return n - miss
};
Copy the code

The first for loop is the number of occurrences of the number, as explained in the explanation, if it is greater than n, it is treated as n.

One thing to note here is that the length of the CNT array is n+1, for no particular reason, just for convenience.

Since the number starts at 1, the array length at n is actually N +1, so to avoid the influence of array 0, the array length is set to N +1.

The second for loop starts at 1 and skips 0.

The final result is n-miss, which stands for numbers that do not appear and cannot be subtracted by large numbers.

But to tell the truth, the performance of this method is not very good, memory consumption to me dry to the last 5%, a little meng ~






PS: To view previous articles and titles, click on the links below:

Here are the categories by date 👇

Front end Brush – Table of Contents (date category)

After some friends remind, the feeling should also be classified according to the question type here is classified according to the question type 👇

Front End Brush problem path – Table of Contents (Question type classification)