Leetcode -1846- Diminishes and rearranges the largest element after the array

[Blog link]

The path to learning at 🐔

The nuggets home page

[B].

I give you an array of positive integers, ARr. You can do something (or nothing) to the ARR so that the array satisfies the following conditions: the first element in the ARR must be1. The absolute value of the difference between any two adjacent elements is less than or equal to1That is, for any1<= I < arr.length (array subscript from0Start), all satisfy abs(AR r[I] -arr [I -1< =])1. Abs of x is the absolute value of x. You can do the following2Any number of operations: Reduces the value of any element in arR to a smaller positive integer. 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. The sample1: 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. The sample2: 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. The sample3: Input: arr = [1.2.3.4.5] output:5Explanation: The array already satisfies all conditions, the maximum element is5. Tip:1 <= arr.length <= 105 
 1 <= arr[i] <= 109Related Topics Greedy array sort 👍22 👎 0
Copy the code

[答 案]

Leetcode topic link

[making address]

Code link

[introduction]

Idea 1: binary search

  • There are two boundary cases
    • Maximum array length
    • If you have the same elements, you may not be able to reach the maximum boundary
  • First sort, and then judge whether it can meet the requirements through the two-point value
public int maximumElementAfterDecrementingAndRearranging(int[] arr) {
            Arrays.sort(arr);
            int l = 0, r = Math.min(arr[arr.length - 1], arr.length);
            while (l < r) {
                int mid = (l - r + 1) / 2 + r;
                if (check(arr, mid)) {
                    l = mid;
                } else {
                    r = mid - 1; }}return r;
        }

        public boolean check(int[] arr, int max) {
            int[] temp = arr;
            temp[0] = 1;
            for (int i = 1; i < arr.length; i++) {
                temp[i] = temp[i - 1] > i  ? i + 1 : Math.min(temp[i], temp[i - 1] + 1);
            }
            return temp[temp.length - 1] >= max;
        }
Copy the code


Time complexity O ( n ∗ l g n ) Time complexity O(n*lg_{n})

Idea 2: Recursion

  • Train of thought is writing to write to discover head to smoke, need not dichotomy
public int maximumElementAfterDecrementingAndRearranging(int[] arr) {
            Arrays.sort(arr);
            int l = 0, r = Math.min(arr[arr.length - 1], arr.length);

            arr[0] = 1;
            for (int i = 1; i < arr.length; i++) {
                arr[i] = arr[i - 1] > i ? i + 1 : Math.min(arr[i], arr[i - 1] + 1);
            }
            return arr[arr.length - 1];
        }
Copy the code


Time complexity O ( n ∗ l g n ) Time complexity O(n*lg_{n})

Idea 3: Counting sort

  • This problem can be optimized to order n.
  • Count sorting
  • I’m not going to show you the monotonically increasing proof, but the Trilobites have a very complicated proof process
  • However, according to the solution of the first two questions, it can be concluded that we supplement the missing element by adding the big element
  • The index+1 element does not exist at index position in the array.
  • Replace the current element with the larger element
  • We define a CNT array that counts the number of elements at each location
  • That is, the number of elements whose index position is index
  • Then we iterate through the CNT array again
  • When the current unknown element does not exist, it is necessary to complete from the subsequent element
  • In this case, we can count the number of missing elements by count
  • Then, whenever there are subsequent larger elements, the larger element with larger element number -1 is taken out to complement the missing element
  • The last missing interval, count, is the element that can’t be completed
  • So the length of the array, the exact number, is what we’re looking for
public int maximumElementAfterDecrementingAndRearranging(int[] arr) {
            int[] cnt = new int[arr.length + 1];
            for (int num : arr) {
                cnt[Math.min(num, arr.length)]++;
            }
            int count = 0;
            for (int i = 1; i <= arr.length; i++) {
                // Does the current element
               if (cnt[i]==0){
                   count++;
               }else{
                   // The extra larger element complements the missing element
                   count -= Math.min(cnt[i]-1,count); }}return arr.length-count;
        }

Copy the code

Time complexity O(n)