2026-02-04: 数组元素相等的最小操作次数。用go语言, 给定一个长

2026-02-04：数组元素相等的最小操作次数。用go语言，给定一个长度为 n 的整型数组 nums。每一步操作可以选取数组中一段相邻且非空的区间，把该区间内的所有元素都替换为这段元素按位与得到的值。请计算需要最少多少次这样的操作，才能让数组中所有位置上的数都相同。

1

1

输入： nums = [1,2]。

输出： 1。

解释：

选择 nums[0...1]：(1 AND 2) = 0，因此数组变为 [0, 0]，所有元素在一次操作后相等。

题目来自力扣3674。

解决思路分步解析

解决这个问题的核心思路是动态规划。我们需要找到最少的操作次数，将整个数组变为相同的值。

1. 目标值确定

首先，需要明确最终所有元素会变成哪个值。一次操作是将一个区间替换为该区间内所有元素的按位与值。多次操作后，整个数组会变为一个最终值，这个值必须是原数组中某个子数组的按位与结果。更具体地说，整个数组最终的相同值，必然是原数组中所有元素按位与的一个“因子”。因此，一个常见的思路是，枚举所有可能成为最终目标的值（通常范围有限，因为 nums[i] 最大为100000），或者更高效地，专注于计算所有子数组的按位与值。

2. 问题转化与状态定义

问题可以转化为：找到最少的操作次数，使得整个数组都变成某个特定的目标值target（这个target是可能出现在最终结果中的值）。然后我们对所有可能的target取最小操作次数。

对于单个target，我们使用动态规划求解。定义dp[i]表示将数组的前i个元素（即nums[0]到nums[i-1]）都变成target 所需的最少操作次数。

3. 状态转移方程

这是最关键的一步。考虑如何计算 dp[i]：

• 基本思想是，要处理前 i 个元素，我们可以先处理好前 j 个元素（j 一次操作将区间 [j, i-1] 内的所有元素替换为该区间的按位与值。如果这个按位与值等于 target，那么这次操作就是有效的。

• 因此，状态转移方程为：

dp[i] = min(dp[j] + 1)，其中 j 满足 0

• 特殊地，如果子数组 nums[0:i] 的按位与值本身就是 target，那么我们可以一次操作完成，即 dp[i] 可以为 1。这包含在上述情况中（当 j=0 时）。

4. 初始化与最终结果

• 初始化：dp[0] = 0，表示前0个元素（空数组）已经处理完毕，操作次数为0。

• 最终结果：对于当前枚举的 target，最小操作次数就是 dp[n]（n 为数组长度）。

• 整体的答案则是 min( dp[n] 对于所有可能的 target )。

5. 算法流程简述

预计算所有子数组的按位与值，或者将其融入动态规划过程中。

枚举所有可能成为最终值的候选 target（通常基于预计算出的子数组按位与结果集合，或者利用数值范围有限的特性）。

对于每个候选 target：

a. 初始化dp数组，dp[0] = 0，其他初始值设为无穷大。

b. 遍历i从 1 到n：

* 计算子数组nums[0:i]的按位与值and_val。

* 遍历j从 0 到i-1：

* 如果and_val等于target，则更新dp[i] = min(dp[i], dp[j] + 1)。

* 为了效率，在遍历j时，可以同时更新and_val：and_val = and_val & nums[i-1]。当and_val已经小于target时，可以提前终止内层循环，因为按位与值只会越来越小。

c. 记录当前target对应的dp[n]。

所有候选 target 对应的 dp[n] 的最小值即为答案。

⏱️ 复杂度分析

• 时间复杂度：该算法的时间复杂度主要取决于动态规划的过程。外层循环枚举候选 target，假设有 T 个候选值。对于每个 target，需要计算 dp 数组，这是一个两重循环。内层循环在优化后（当按位与值小于 target 时提前终止），最坏情况下复杂度为 O(n²)。因此，总的最坏时间复杂度为 O(T * n²)。由于 nums[i] 的值域限制，T 的值不会太大（最多为不同子数组按位与值的个数，远小于 100000）。对于 n

• 额外空间复杂度：算法需要额外的空间主要是 dp 数组，大小为 O(n)。此外，可能需要一个集合来存储候选 target。因此，总的额外空间复杂度为 O(n)。

Go完整代码如下：

package main

import (

"fmt"

)

func minOperations(nums []int)int {

for _, x := range nums {

if x != nums[0] {

return1

}

}

return0

}

func main {

nums := []int{1, 2}

result := minOperations(nums)

fmt.Println(result)

}

Python完整代码如下：

# -*-coding:utf-8-*-

def min_operations(nums):

if not nums:

return0

first = nums[0]

for x in nums:

if x != first:

return1

return0

if __name__ == "__main__":

nums = [1, 2]

result = min_operations(nums)

print(result)

C++完整代码如下：

#include

using namespace std;

int minOperations(const vector& nums) {

if (nums.empty) return0; // 若为空数组，视为已相等

for (int x : nums) {

if (x != nums[0]) return1;

}

return0;

}

int main {

vector nums = {1, 2};

int result = minOperations(nums);

cout

return0;

}

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。

欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。