“This is the 40th day of my participation in the First Challenge 2022. For details: First Challenge 2022”

Topic describes

This is 2170 on LeetCode. The minimum operand required to make an array alternate is medium difficulty.

Tag: “Greedy.”

You are given an array numsnumsnums with subscripts starting at 000, consisting of NNN positive integers.

The array numsnumsnums is an alternating array if the following conditions are met:

  • Nums [I] – 2 = = nums [I] nums = = [I – 2] nums nums [I] [I] – 2 = = nums [I], among them 2 < = I < = n < = I < = n – 12-12 < = I < = n – 1.
  • Nums [I – 1)! =nums[i]nums[i – 1] ! Nums = nums [I] [I – 1)! =nums[I], where 1<= I <= N −11 <= I <= n-11 <= I <= N −1.

In one step, you can select subscript III and change nums[I]nums[I]nums[I] to any positive integer.

Returns the minimum operand needed to make an array alternating.

Example 1:

Input: nums = [3,1,3,2,4,3] Output: 3 Explanation: One way to make an array alternating is to convert the array to [3,1,3,1,3,1]. In this case, the operand is 3. It can be shown that you cannot make an array alternate with less than 3 operands.Copy the code

Example 2:

Input: nums = [1,2,2,2,2] output: 2 explanation: one way to make an array alternating is to convert the array to [1,2,1,2,1]. In this case, the operand is 2. Note that arrays cannot be converted to [2,2,2,2,2]. Because in this case, nums[0] == nums[1], the condition for alternating arrays is not met.Copy the code

Tip:


  • 1 < = n u m s . l e n g t h < = 1 0 5 1 <= nums.length <= 10^5

  • 1 < = n u m s [ i ] < = 1 0 5 1 <= nums[i] <= 10^5

greedy

According to the definition of “alternating array”, we can divide the array into two sequences according to the parity of subscripts. The ultimate goal is to use the minimum number of modifications so that “both sequences become arithmetic sequences with tolerance of 000” and “the first terms of the two sequences are not equal”.

To modify a sequence to an arithmetic sequence with a tolerance of 000 with a minimum number of times is equivalent to modifying the least number of numbers, equivalent to reserving the most numbers, and it is easy to think of modifying other “non-mode” numbers in the sequence to “mode” (if there are more than one mode, take any).

However, simply applying the above logic to two sequences does not guarantee that the final result is an “alternate array”, that is, it may not satisfy the requirement that “the first items of two sequences are not equal”.

Therefore, we can scan numsnumsnums and count the maximum (mode) and sublarge value of “even subscript sequence” and “odd subscript sequence” respectively. Use a and B to refer to the maximum and submaximum of the “even subscript sequence”, and use C and D to refer to the maximum and submaximum of the “odd subscript sequence”. At the same time, m1 and m2 are used to count the occurrence times of a certain number in “even subscript sequence” and “odd subscript sequence” respectively.

According to whether the maximum value of the two sequences conflicts, the case is discussed:

  • If the maximum values of the two sequences do not conflict (A ≠ CA \neq ca=c), then both sequences can obtain the minimum number of modifications (reserved maximum). The overall minimum number of modifications is n− M1 [a]−m2[c] n-m1 [a] -m2 [c]n− M1 [a]−m2[c].
  • If the maximum values of the two sequences conflict (a =ca\ =ca =c) : Then only one sequence can obtain the minimum number of modifications (reserved maximum value), and the other sequence can only obtain the “sub-small” number of modifications (reserved sub-large value), The whole, the minimum number of changes to n – Max ⁡ (m1 + m2 [d], [a] [b] m1 + m2 [c]) n – \ Max (m1 + m2 [d], [a] [b] m1 + m2 [c]) n – Max (m1 + m2 [d], [a] [b] m1 + m2 [c]).

Code:

class Solution {
    static int N = 100010;
    static int[] m1 = new int[N], m2 = new int[N];
    public int minimumOperations(int[] nums) {
        int n = nums.length;
        Arrays.fill(m1, 0);
        Arrays.fill(m2, 0);
        int a = 0, b = 0, c = 0, d = 0;
        for (int i = 0; i < n; i++) {
            int t = nums[i];
            if (i % 2= =0) {
                m1[t]++;
                if (a == 0 || m1[t] > m1[a]) {
                    b = a; a = t;
                } else if(t ! = a && (b ==0|| m1[t] > m1[b])) { b = t; }}else {
                m2[t]++;
                if (c == 0 || m2[t] > m2[c]) {
                    d = c; c = t;
                } else if(t ! = c && (d ==0|| m2[t] > m2[d])) { d = t; }}}if(a ! = c)return n - m1[a] - m2[c];
        else returnn - Math.max(m1[a] + m2[d], m1[b] + m2[c]); }}Copy the code
  • Time complexity: O(n)O(n)O(n)
  • Space complexity: O(C)O(C)O(C)

The last

This is the No.2170 of our “Brush through LeetCode” series. The series started on 2021/01/01.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.