Question

2170. 使数组变成交替数组的最少操作数

English Version

题目描述

给你一个下标从 0 开始的数组 nums ，该数组由 n 个正整数组成。

如果满足下述条件，则数组 nums 是一个 交替数组 ：

• nums[i - 2] == nums[i] ，其中 2 <= i <= n - 1 。
• nums[i - 1] != nums[i] ，其中 1 <= i <= n - 1 。

在一步 操作 中，你可以选择下标 i 并将 nums[i] 更改 为 任一 正整数。

返回使数组变成交替数组的 最少操作数 。

 

示例 1：

输入：nums = [3,1,3,2,4,3]
输出：3
解释：
使数组变成交替数组的方法之一是将该数组转换为 [3,1,3,_1_,_3_,_1_] 。
在这种情况下，操作数为 3 。
可以证明，操作数少于 3 的情况下，无法使数组变成交替数组。

示例 2：

输入：nums = [1,2,2,2,2]
输出：2
解释：
使数组变成交替数组的方法之一是将该数组转换为 [1,2,_1_,2,_1_].
在这种情况下，操作数为 2 。
注意，数组不能转换成 [_2_,2,2,2,2] 。因为在这种情况下，nums[0] == nums[1]，不满足交替数组的条件。

 

提示：

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

解法

方法一

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]);
  }
}