3674. 使数组元素相等的最小操作数

Easy

题目描述

给你一个长度为 n 的整数数组 nums。

在一次操作中，你可以选择任意子数组 nums[l…r]（0 <= l <= r < n），并将该子数组中的每个元素替换为所有元素的按位与（AND）运算结果。

返回使 nums 的所有元素相等所需的最小操作数。

子数组是数组中连续的非空元素序列。

示例 1：

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

示例 2：

输入：nums = [5,5,5]
输出：0
解释：nums 是 [5, 5, 5]，所有元素已经相等，因此需要 0 次操作。

约束条件：

• 1 <= n == nums.length <= 100
• 1 <= nums[i] <= 10^5

提示：

• 如果 nums 的所有元素已经相等，需要多少次操作？
• 答案要么是 0，要么是 1。
• 如果数组中的所有值最初相等，答案是 0，否则是 1，因为你可以在一步中对整个数组应用 AND 操作。

解题思路

这是一道典型的脑筋急转弯题目。关键在于理解按位与（AND）运算的性质：

核心思路：

1. 如果数组中所有元素已经相等，则不需要任何操作，返回 0
2. 如果数组中存在不相等的元素，我们只需要 1 次操作就能让所有元素相等

为什么只需要 1 次操作？

• 我们可以选择整个数组作为子数组（l=0, r=n-1）
• 对整个数组进行按位与运算，所有元素都会变成相同的值
• 无论原数组元素如何分布，经过一次全数组的 AND 操作后，所有位置的元素都会变成相同值

算法步骤：

1. 检查数组中是否所有元素都相等
2. 如果相等返回 0，否则返回 1

这个解法的巧妙之处在于：不需要考虑具体的 AND 运算结果是什么，也不需要考虑分步操作的策略。题目的约束和 AND 运算的性质保证了我们总能在最多 1 次操作内达到目标。

代码实现

class Solution {
public:
    int minOperations(vector<int>& nums) {
        int first = nums[0];
        for (int num : nums) {
            if (num != first) {
                return 1;
            }
        }
        return 0;
    }
};

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        first = nums[0]
        for num in nums:
            if num != first:
                return 1
        return 0

public class Solution {
    public int MinOperations(int[] nums) {
        int first = nums[0];
        foreach (int num in nums) {
            if (num != first) {
                return 1;
            }
        }
        return 0;
    }
}

var minOperations = function(nums) {
    const first = nums[0];
    for (const num of nums) {
        if (num !== first) {
            return 1;
        }
    }
    return 0;
};

复杂度分析

• 时间复杂度： O(n)，需要遍历数组一次检查所有元素是否相等
• 空间复杂度： O(1)，只使用常数额外空间