2025-07-08: 使数组元素互不相同所需的最少操作次数。用go语言

2025-07-08：使数组元素互不相同所需的最少操作次数。用go语言，给定一个整数数组 nums，要求通过若干次操作使数组中的元素全部唯一。每次操作都需要从数组开头移除最多三个元素；如果剩余元素不足三个，则将其全部删除。最终，数组为空或所有元素互不重复时即满足条件。请你计算完成此目标所需的最少操作次数。

1

1

输入： nums = [1,2,3,4,2,3,3,5,7]。

输出： 2。

解释：

第一次操作：移除前 3 个元素，数组变为 [4, 2, 3, 3, 5, 7]。

第二次操作：再次移除前 3 个元素，数组变为 [3, 5, 7]，此时数组中的元素互不相同。

因此，答案是 2。

题目来自力扣3396。

解决思路

1. 从后向前检查重复：为了确定需要移除多少元素才能确保剩余元素唯一，我们可以从数组的末尾开始向前检查。这样可以更容易地找到第一个导致重复的元素。

2. 标记已见过的元素：使用一个布尔数组 seen 来记录已经出现过的元素。从后向前遍历数组时，如果遇到一个已经标记为 true 的元素，说明这个元素在之前已经出现过，因此需要移除从开头到当前位置的元素。

3. 计算操作次数：每次操作可以移除最多三个元素。因此，如果需要移除 i 个元素（从开头到当前位置），那么操作次数为 ceil(i / 3)。

具体步骤

1. 初始化一个布尔数组 seen，大小为 128（因为题目中 nums[i] 的最大值为 100，所以 128 足够覆盖所有可能的值）。

2. 从数组的末尾开始向前遍历：

• 对于当前元素 nums[i]，检查 seen[nums[i]] 是否为 true：

• 如果是，说明 nums[i] 是一个重复元素，需要移除从开头到 i 的所有元素。操作次数为 i / 3 + 1（因为每次最多移除 3 个元素，所以 ceil(i / 3) 就是 i / 3 + 1）。

• 如果不是，将 seen[nums[i]] 标记为 true，继续向前遍历。

3. 如果遍历完整个数组都没有发现重复元素，说明不需要任何操作，返回 0。

示例的逐步执行

以 nums = [1, 2, 3, 4, 2, 3, 3, 5, 7] 为例：

1. 初始化 seen 为全 false。

2. 从后向前遍历：

• 返回操作次数 2。

时间复杂度和空间复杂度

• 时间复杂度：O(n)，其中 n 是数组的长度。我们只需要从后向前遍历数组一次。

• 空间复杂度：O(1)，因为 seen 数组的大小是固定的（128），与输入规模无关。

Go完整代码如下：

.

package mainimport ( "fmt")func minimumOperations(nums []int)int { seen := make([]bool, 128) for i := len(nums) - 1; i >= 0; i-- { if seen[nums[i]] { return i/3 + 1 } seen[nums[i]] = true } return0}func main { nums := []int{1, 2, 3, 4, 2, 3, 3, 5, 7} result := minimumOperations(nums) fmt.Println(result)}

Python完整代码如下：

.

# -*-coding:utf-8-*-def minimum_operations(nums): seen = set for i in range(len(nums) - 1, -1, -1): if nums[i] in seen: return i // 3 + 1 seen.add(nums[i]) return 0if __name__ == "__main__": nums = [1, 2, 3, 4, 2, 3, 3, 5, 7] result = minimum_operations(nums) print(result)

·

我们相信Go语言和算法为普通开发者提供了困境的“面试利器”，并致力于分享全面的编程知识。在这里，您可以找到最新的Go语言教程、算法解析、提升面试竞争力的秘籍以及行业动态。

欢迎关注“福大规模架构师每日一题”，让 Go 语言和算法助力您的职业发展