Medium

题目描述

给你一个下标从 0 开始的正整数数组 nums 。你可以对数组执行以下操作 任意 次：

  • 选择满足 0 <= i < n - 1 的下标 i ，将 nums[i] 或者 nums[i + 1] 两者之一替换为它们的 最大公约数。

请你返回使数组 nums 中所有元素都等于 1 的 最少 操作次数。如果无法让所有元素都等于 1 ，请你返回 -1 。

两个正整数的最大公约数指的是能整除这两个数的最大正整数。

示例 1：

输入：nums = [2,6,3,4]
输出：4
解释：我们可以执行以下操作：
- 选择下标 i = 2 ，将 nums[2] 替换为 gcd(3,4) = 1 ，数组变为 [2,6,1,4] 。
- 选择下标 i = 1 ，将 nums[1] 替换为 gcd(6,1) = 1 ，数组变为 [2,1,1,4] 。
- 选择下标 i = 0 ，将 nums[0] 替换为 gcd(2,1) = 1 ，数组变为 [1,1,1,4] 。
- 选择下标 i = 2 ，将 nums[3] 替换为 gcd(1,4) = 1 ，数组变为 [1,1,1,1] 。

示例 2：

输入：nums = [2,10,6,14]
输出：-1
解释：可以证明无法让所有元素都等于 1 。

提示：

  • 2 <= nums.length <= 50
  • 1 <= nums[i] <= 10^6

解题思路

这道题的关键洞察在于：如果数组中已经存在 1，那么我们可以用 1 与相邻元素做 gcd 运算，一步一步地将所有元素都变成 1。

具体分析：

  1. 如果数组中已有 1：由于 gcd(1, x) = 1 对任意正整数 x 成立，我们可以让 1 “传播” 到相邻位置，最终覆盖整个数组。需要的操作次数就是 n - count(1)，其中 count(1) 是数组中 1 的个数。

  2. 如果数组中没有 1：我们需要先通过 gcd 运算创造出一个 1。关键是找到最短的连续子数组，使其所有元素的 gcd 等于 1。

  3. 判断是否可能：如果整个数组的 gcd 大于 1，那么无论如何操作都无法得到 1，返回 -1。

  4. 寻找最短子数组：我们枚举所有可能的连续子数组，计算其 gcd，找到长度最短且 gcd 为 1 的子数组。假设这个子数组长度为 k，那么需要 k-1 次操作将其变成 1，再加上 n-1 次操作将 1 传播到整个数组，总共 k-1+n-1 = n+k-2 次操作。

推荐解法：先检查是否已有 1，再寻找最短的 gcd 为 1 的子数组。

代码实现

class Solution {
public:
    int minOperations(vector<int>& nums) {
        int n = nums.size();
        int ones = 0;
        
        // 统计数组中1的个数
        for (int num : nums) {
            if (num == 1) ones++;
        }
        
        // 如果已经有1，直接传播即可
        if (ones > 0) {
            return n - ones;
        }
        
        // 寻找最短的gcd为1的子数组
        int minLen = INT_MAX;
        
        for (int i = 0; i < n; i++) {
            int currentGcd = nums[i];
            for (int j = i; j < n; j++) {
                currentGcd = __gcd(currentGcd, nums[j]);
                if (currentGcd == 1) {
                    minLen = min(minLen, j - i + 1);
                    break;
                }
            }
        }
        
        // 如果找不到gcd为1的子数组，返回-1
        if (minLen == INT_MAX) {
            return -1;
        }
        
        // 需要minLen-1次操作生成1，再需要n-1次操作传播
        return minLen - 1 + n - 1;
    }
};

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        import math
        
        n = len(nums)
        ones = nums.count(1)
        
        # 如果已经有1，直接传播即可
        if ones > 0:
            return n - ones
        
        # 寻找最短的gcd为1的子数组
        min_len = float('inf')
        
        for i in range(n):
            current_gcd = nums[i]
            for j in range(i, n):
                current_gcd = math.gcd(current_gcd, nums[j])
                if current_gcd == 1:
                    min_len = min(min_len, j - i + 1)
                    break
        
        # 如果找不到gcd为1的子数组，返回-1
        if min_len == float('inf'):
            return -1
        
        # 需要min_len-1次操作生成1，再需要n-1次操作传播
        return min_len - 1 + n - 1

public class Solution {
    public int MinOperations(int[] nums) {
        int n = nums.Length;
        int ones = 0;
        
        // 统计数组中1的个数
        foreach (int num in nums) {
            if (num == 1) ones++;
        }
        
        // 如果已经有1，直接传播即可
        if (ones > 0) {
            return n - ones;
        }
        
        // 寻找最短的gcd为1的子数组
        int minLen = int.MaxValue;
        
        for (int i = 0; i < n; i++) {
            int currentGcd = nums[i];
            for (int j = i; j < n; j++) {
                currentGcd = Gcd(currentGcd, nums[j]);
                if (currentGcd == 1) {
                    minLen = Math.Min(minLen, j - i + 1);
                    break;
                }
            }
        }
        
        // 如果找不到gcd为1的子数组，返回-1
        if (minLen == int.MaxValue) {
            return -1;
        }
        
        // 需要minLen-1次操作生成1，再需要n-1次操作传播
        return minLen - 1 + n - 1;
    }
    
    private int Gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}

var minOperations = function(nums) {
    function gcd(a, b) {
        while (b !== 0) {
            [a, b] = [b, a % b];
        }
        return a;
    }
    
    let ones = nums.filter(x => x === 1).length;
    
    if (ones > 0) {
        return nums.length - ones;
    }
    
    let minOps = Infinity;
    
    for (let i = 0; i < nums.length; i++) {
        let currentGcd = nums[i];
        for (let j = i + 1; j < nums.length; j++) {
            currentGcd = gcd(currentGcd, nums[j]);
            if (currentGcd === 1) {
                minOps = Math.min(minOps, j - i + nums.length - 1);
                break;
            }
        }
    }
    
    return minOps === Infinity ? -1 : minOps;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n²) - 需要枚举所有子数组，每个子数组计算gcd
空间复杂度O(1) - 只使用常数额外空间