LeetCode 6005. The minimum operand to make an array an alternating array

6005. The minimum number of operands to make an array an alternating array

I'll give you a subscript from 0 Starting array nums , The array consists of n It's made up of four positive integers .

If the following conditions are met , The array nums It's a Alternating array ：

• nums[i - 2] == nums[i] , among 2 <= i <= n - 1 .
• nums[i - 1] != nums[i] , among 1 <= i <= n - 1 .

In one step operation in , You can choose the subscript i And will nums[i] change by any Positive integer .

Returns the that makes the array an alternating array The minimum number of operands .

Example 1：

 Input ：nums = [3,1,3,2,4,3]
 Output ：3
 explain ：
 One way to turn an array into an alternating array is to convert the array to  [3,1,3,1,3,1] .
 under these circumstances , The operands are  3 .
 Can prove that , Operands are less than  3  Under the circumstances , Cannot make an array into an alternating array .

Example 2：

 Input ：nums = [1,2,2,2,2]
 Output ：2
 explain ：
 One way to turn an array into an alternating array is to convert the array to  [1,2,1,2,1].
 under these circumstances , The operands are  2 .
 Be careful , Array cannot be converted to  [2,2,2,2,2] . Because in this case ,nums[0] == nums[1], The condition of alternating array is not satisfied .

Tips ：

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 105

Two 、 Method 1

Count the most frequent occurrences of , Then find the one that appears the most and the second most , If it's not equal, subtract these , If equal, subtract the maximum sum

class Solution {
    
    public int minimumOperations(int[] nums) {
    
        Map<Integer, Integer> map1 = new HashMap<>();
        Map<Integer, Integer> map2 = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
    
            if ((i & 1) == 1) {
    
                map1.put(nums[i], map1.getOrDefault(nums[i], 0) + 1);
            } else {
    
                 map2.put(nums[i], map2.getOrDefault(nums[i], 0) + 1);
            }
        }
        int x1 = 0;
        int x2 = 0;
        int y1 = 0;
        int y2 = 0;
        int a = 0;
        int b = 0;
        int c = 0;
        int d = 0;
        for (Map.Entry<Integer,Integer> entry : map1.entrySet()) {
    
            if (entry.getValue() > a) {
    
                b = a;
                a = entry.getValue();
                x1 = entry.getKey();
               
            }
           else  if (entry.getValue() > b) {
    
                b = entry.getValue();
            }
        }
        for (Map.Entry<Integer,Integer> entry : map2.entrySet()) {
    
            if (entry.getValue() > c) {
    
                d = c;
                c = entry.getValue();
                y1 = entry.getKey();
            }
           else  if (entry.getValue() > d) {
    
                d = entry.getValue();
            }
        }
        if (x1 == y1) {
    
            return nums.length - Math.max(a + d, b + c);
        } else {
    
            return nums.length - (a + c);
        }
    }
}

Complexity analysis

• Time complexity ：O(n).

• Spatial complexity ：O(n).