跳转至

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

题目描述

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

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

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

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

 

示例 1：

输入： nums = [1,2]

输出： 1

解释：

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

示例 2：

输入： nums = [5,5,5]

输出： 0

解释：

nums 本身是 [5, 5, 5]，所有元素已经相等，因此不需要任何操作。

 

提示：

  • 1 <= n == nums.length <= 100
  • 1 <= nums[i] <= 105

解法

方法一：一次遍历

如果 \(\textit{nums}\) 中所有元素都相等，则不需要任何操作；否则，选择整个数组作为子数组进行一次操作即可。

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

1
2
3
class Solution:
    def minOperations(self, nums: List[int]) -> int:
        return int(any(x != nums[0] for x in nums))

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution {
    public int minOperations(int[] nums) {
        for (int x : nums) {
            if (x != nums[0]) {
                return 1;
            }
        }
        return 0;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
public:
    int minOperations(vector<int>& nums) {
        for (int x : nums) {
            if (x != nums[0]) {
                return 1;
            }
        }
        return 0;
    }
};

1
2
3
4
5
6
7
8
func minOperations(nums []int) int {
    for _, x := range nums {
        if x != nums[0] {
            return 1
        }
    }
    return 0
}

1
2
3
4
5
6
7
8
function minOperations(nums: number[]): number {
    for (const x of nums) {
        if (x !== nums[0]) {
            return 1;
        }
    }
    return 0;
}

评论