What is the minimum number of operations required to make an array alternating?

The minimum number of operations is determined by counting the frequency of elements at odd and even positions, then swapping elements if necessary.

How do I solve the Minimum Operations to Make the Array Alternating problem?

First, split the array into odd and even indexed groups. Count frequencies, identify the most frequent elements, and then minimize changes by swapping elements if necessary.

What is the primary pattern used in the Minimum Operations to Make the Array Alternating problem?

The primary pattern involves array scanning combined with hash lookup to count element frequencies and optimize the number of operations.

What are the constraints of the Minimum Operations to Make the Array Alternating problem?

The array length must be between 1 and 10^5, and each element in the array must be between 1 and 10^5.

What are common pitfalls when solving the Minimum Operations to Make the Array Alternating problem?

Common pitfalls include failing to handle element overlaps between odd and even indexed groups, not counting frequencies correctly, and misunderstanding the operations needed for alternating sequences.

#2170

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

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

给你一个下标从 0 开始的数组 nums ，该数组由 n 个正整数组成。如果满足下述条件，则数组 nums 是一个交替数组： nums[i - 2] == nums[i] ，其中 2 。 nums[i - 1] != nums[i] ，其中 1 。在一步操作中，你可以选择下标 i 并将 …

数组哈希表贪心计数

题目描述

给你一个下标从 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 <= 10⁵
1 <= nums[i] <= 10⁵

lightbulb

解题思路

方法一：维护奇偶位置的计数

根据题目描述，我们可以知道，如果数组 $\textit{nums}$ 是一个交替数组，那么数组中的奇数位置和偶数位置的元素一定是不同的，且奇数位置的元素相同，偶数位置的元素也相同。

要使得数组 $\textit{nums}$ 变成交替数组的操作数最少，我们可以通过统计奇数位置和偶数位置的元素的出现次数，找到偶数位置出现次数最多的两个元素 $a_0$ 和 $a_2$ ，以及对应的出现次数 $a_1$ 和 $a_3$ ；再找到奇数位置出现次数最多的两个元素 $b_0$ 和 $b_2$ ，以及对应的出现次数 $b_1$ 和 $b_3$ 。

如果 $a_0 \neq b_0$ ，那么我们可以将数组 $\textit{nums}$ 中偶数位置的元素全部变成 $a_0$ ，奇数位置的元素全部变成 $b_0$ ，这样操作数为 $n - (a_1 + b_1)$ ；如果 $a_0 = b_0$ ，那么我们可以将数组 $\textit{nums}$ 中偶数位置的元素全部变成 $a_0$ ，奇数位置的元素全部变成 $b_2$ ，或者将数组 $\textit{nums}$ 中偶数位置的元素全部变成 $a_2$ ，奇数位置的元素全部变成 $b_0$ ，这样操作数为 $n - \max(a_1 + b_3, a_3 + b_1)$ 。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为数组 $\textit{nums}$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

class Solution:
    def minimumOperations(self, nums: List[int]) -> int:
        def f(i: int) -> Tuple[int, int, int, int]:
            k1 = k2 = 0
            cnt = Counter(nums[i::2])
            for k, v in cnt.items():
                if cnt[k1] < v:
                    k2, k1 = k1, k
                elif cnt[k2] < v:
                    k2 = k
            return k1, cnt[k1], k2, cnt[k2]

        a, b = f(0), f(1)
        n = len(nums)
        if a[0] != b[0]:
            return n - (a[1] + b[1])
        return n - max(a[1] + b[3], a[3] + b[1])

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
This problem tests the ability to work with arrays and hash tables efficiently.
question_mark
Check the candidate's ability to optimize solutions using counting techniques.
question_mark
Look for a clear understanding of how to handle alternating sequence constraints.

warning

常见陷阱

外企场景

error
Failing to split the array into odd and even indexed groups properly.
error
Not considering swapping the most frequent elements when they overlap.
error
Misunderstanding the number of operations needed when both the odd and even indexed groups share common elements.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Using different methods for frequency counting.
arrow_right_alt
Handling larger input sizes efficiently.
arrow_right_alt
Considering edge cases like arrays of length 1 or 2.

help

常见问题

外企场景

继续练习

#2131 连接两字母单词得到的最长回文串 #2244 完成所有任务需要的最少轮数 #2499 让数组不相等的最小总代价