Question

2170. Minimum Operations to Make the Array Alternating

中文文档

Description

You are given a 0-indexed array nums consisting of n positive integers.

The array nums is called alternating if:

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

In one operation, you can choose an index i and change nums[i] into any positive integer.

Return _the minimum number of operations required to make the array alternating_.

 

Example 1:

Input: nums = [3,1,3,2,4,3]
Output: 3
Explanation:
One way to make the array alternating is by converting it to [3,1,3,1,3,1].
The number of operations required in this case is 3.
It can be proven that it is not possible to make the array alternating in less than 3 operations. 

Example 2:

Input: nums = [1,2,2,2,2]
Output: 2
Explanation:
One way to make the array alternating is by converting it to [1,2,1,2,1].
The number of operations required in this case is 2.
Note that the array cannot be converted to [2,2,2,2,2] because in this case nums[0] == nums[1] which violates the conditions of an alternating array.

 

Constraints:

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

Solutions

Solution 1

class Solution:
  def minimumOperations(self, nums: List[int]) -> int:
    def get(i):
      c = Counter(nums[i::2]).most_common(2)
      if not c:
        return [(0, 0), (0, 0)]
      if len(c) == 1:
        return [c[0], (0, 0)]
      return c

    n = len(nums)
    return min(n - (n1 + n2) for a, n1 in get(0) for b, n2 in get(1) if a != b)

class Solution {
  private int[] nums;
  private int n;

  public int minimumOperations(int[] nums) {
    this.nums = nums;
    n = nums.length;
    int ans = Integer.MAX_VALUE;
    for (int[] e1 : get(0)) {
      for (int[] e2 : get(1)) {
        if (e1[0] != e2[0]) {
          ans = Math.min(ans, n - (e1[1] + e2[1]));
        }
      }
    }
    return ans;
  }

  private int[][] get(int i) {
    Map<Integer, Integer> freq = new HashMap<>();
    for (; i < n; i += 2) {
      freq.put(nums[i], freq.getOrDefault(nums[i], 0) + 1);
    }
    int a = 0;
    int n1 = 0;
    int b = 0;
    int n2 = 0;
    for (Map.Entry<Integer, Integer> e : freq.entrySet()) {
      int k = e.getKey();
      int v = e.getValue();
      if (v > n1) {
        b = a;
        n2 = n1;
        a = k;
        n1 = v;
      } else if (v > n2) {
        b = k;
        n2 = v;
      }
    }
    return new int[][] {{a, n1}, {b, n2}};
  }
}

typedef pair<int, int> PII;

class Solution {
public:
  int minimumOperations(vector<int>& nums) {
    int ans = INT_MAX;
    int n = nums.size();
    for (auto& [a, n1] : get(0, nums))
      for (auto& [b, n2] : get(1, nums))
        if (a != b)
          ans = min(ans, n - (n1 + n2));
    return ans;
  }

  vector<PII> get(int i, vector<int>& nums) {
    unordered_map<int, int> freq;
    for (; i < nums.size(); i += 2) ++freq[nums[i]];
    int a = 0, n1 = 0, b = 0, n2 = 0;
    for (auto& [k, v] : freq) {
      if (v > n1) {
        b = a;
        n2 = n1;
        a = k;
        n1 = v;
      } else if (v > n2) {
        b = k;
        n2 = v;
      }
    }
    return {{a, n1}, {b, n2}};
  }
};

func minimumOperations(nums []int) int {
  n := len(nums)
  get := func(i int) [][]int {
    freq := make(map[int]int)
    for ; i < n; i += 2 {
      freq[nums[i]]++
    }
    a, n1, b, n2 := 0, 0, 0, 0
    for k, v := range freq {
      if v > n1 {
        b, n2, a, n1 = a, n1, k, v
      } else if v > n2 {
        b, n2 = k, v
      }
    }
    return [][]int{{a, n1}, {b, n2}}
  }
  ans := 100000
  for _, e1 := range get(0) {
    for _, e2 := range get(1) {
      if e1[0] != e2[0] && ans > (n-(e1[1]+e2[1])) {
        ans = n - (e1[1] + e2[1])
      }
    }
  }
  return ans
}

function minimumOperations(nums: number[]): number {
  const n = nums.length,
    m = 10 ** 5;
  let odd = new Array(m).fill(0);
  let even = new Array(m).fill(0);
  for (let i = 0; i < n; i++) {
    let cur = nums[i];
    if (i & 1) {
      odd[cur] = (odd[cur] || 0) + 1;
    } else {
      even[cur] = (even[cur] || 0) + 1;
    }
  }
  let i1 = odd.indexOf(Math.max(...odd));
  let i2 = even.indexOf(Math.max(...even));
  if (i1 != i2) {
    return n - odd[i1] - even[i2];
  } else {
    let l1 = odd[i1],
      l2 = even[i2];
    (odd[i1] = 0), (even[i2] = 0);
    let j1 = odd.indexOf(Math.max(...odd));
    let j2 = even.indexOf(Math.max(...even));
    return n - Math.max(l1 + even[j2], l2 + odd[j1]);
  }
}