2026-02-04：数组元素相等的最小操作次数。用go语言，给定一个长度为 n 的整型数组 nums。每一步操作可以选取数组中一段相邻且非空的区间

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

1 <= n == nums.length <= 100。

1 <= nums[i] <= 100000。

输入： nums = [1,2]。

输出： 1。

解释：

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

题目来自力扣3674。

🔄 解决思路分步解析

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

1. 1. 目标值确定 首先，需要明确最终所有元素会变成哪个值。一次操作是将一个区间替换为该区间内所有元素的按位与值。多次操作后，整个数组会变为一个最终值，这个值必须是原数组中某个子数组的按位与结果。更具体地说，整个数组最终的相同值，必然是原数组中所有元素按位与的一个“因子”。因此，一个常见的思路是，枚举所有可能成为最终目标的值（通常范围有限，因为 nums[i] 最大为100000），或者更高效地，专注于计算所有子数组的按位与值。
2. 2. 问题转化与状态定义 问题可以转化为：找到最少的操作次数，使得整个数组都变成某个特定的目标值target（这个target是可能出现在最终结果中的值）。然后我们对所有可能的target取最小操作次数。 对于单个target，我们使用动态规划求解。定义dp[i]表示将数组的前i个元素（即nums[0]到nums[i-1]）都变成target 所需的最少操作次数。
3. 3. 状态转移方程 这是最关键的一步。考虑如何计算 dp[i]：
   • • 基本思想是，要处理前 i 个元素，我们可以先处理好前 j 个元素（j < i），然后一次操作将区间 [j, i-1] 内的所有元素替换为该区间的按位与值。如果这个按位与值等于 target，那么这次操作就是有效的。
   • • 因此，状态转移方程为： dp[i] = min(dp[j] + 1)，其中 j 满足 0 <= j < i，并且子数组 nums[j:i]（即从索引 j 到 i-1）的按位与结果等于 target。
   • • 特殊地，如果子数组 nums[0:i] 的按位与值本身就是 target，那么我们可以一次操作完成，即 dp[i] 可以为 1。这包含在上述情况中（当 j=0 时）。
4. 4. 初始化与最终结果
   • • 初始化：dp[0] = 0，表示前0个元素（空数组）已经处理完毕，操作次数为0。
   • • 最终结果：对于当前枚举的 target，最小操作次数就是 dp[n]（n 为数组长度）。
   • • 整体的答案则是 min( dp[n] 对于所有可能的 target )。
5. 5. 算法流程简述
   1. 1. 预计算所有子数组的按位与值，或者将其融入动态规划过程中。
   2. 2. 枚举所有可能成为最终值的候选 target（通常基于预计算出的子数组按位与结果集合，或者利用数值范围有限的特性）。
   3. 3. 对于每个候选 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]。
   4. 4. 所有候选 target 对应的 dp[n] 的最小值即为答案。

⏱️ 复杂度分析

• • 时间复杂度：该算法的时间复杂度主要取决于动态规划的过程。外层循环枚举候选 target，假设有 T 个候选值。对于每个 target，需要计算 dp 数组，这是一个两重循环。内层循环在优化后（当按位与值小于 target 时提前终止），最坏情况下复杂度为 O(n²)。因此，总的最坏时间复杂度为 O(T * n²)。由于 nums[i] 的值域限制，T 的值不会太大（最多为不同子数组按位与值的个数，远小于 100000）。对于 n <= 100，这个复杂度是可接受的。
• • 额外空间复杂度：算法需要额外的空间主要是 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 <bits/stdc++.h>
using namespace std;

int minOperations(const vector<int>& nums) {
    if (nums.empty()) return0; // 若为空数组，视为已相等
    for (int x : nums) {
        if (x != nums[0]) return1;
    }
    return0;
}

int main() {
    vector<int> nums = {1, 2};
    int result = minOperations(nums);
    cout << result << endl;
    return0;
}

在这里插入图片描述