leetcode
leetcode 1151 ~ 1200
检查「好数组」

检查「好数组」

难度:

标签:

题目描述

代码结果

运行时间: 36 ms, 内存: 25.3 MB


/*
 * In this solution, we use Java Streams to simplify the code and make it more functional.
 * The logic remains the same as in the imperative approach: we calculate the GCD of all numbers
 * in the array and check if it is equal to 1. If so, we return true; otherwise, false.
 */

import java.util.stream.*;

public class GoodArrayCheckerStream {
    public boolean isGoodArray(int[] nums) {
        int gcd = Arrays.stream(nums)
                        .reduce(0, (a, b) -> gcd(a, b));
        return gcd == 1;
    }

    private int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}

解释

方法:

这道题的核心思路是利用贝祖定理(Bézout's identity),该定理指出对于任意整数a和b,如果d是它们的最大公约数,那么一定存在整数x和y,使得ax + by = d。根据这个定理,如果数组中所有元素的最大公约数为1,那么就可以通过这些元素的线性组合得到1,即存在一种组合使得最终和为1。因此,我们只需要计算数组中所有数的最大公约数是否为1即可。实现上,我们从数组的第一个元素开始,依次计算与下一个元素的最大公约数,直到遍历完整个数组,如果过程中最大公约数变为1,就可以提前结束遍历返回True。如果遍历完成后最大公约数仍然是1,则返回True,否则返回False。

时间复杂度:

O(n * logN)

空间复杂度:

O(1)

代码细节讲解

🦆
在使用贝祖定理判断数组是否是「好数组」时,是否所有数组元素都需要参与gcd计算?例如,是否有可能通过数组的一个子集就能得出gcd为1?
在使用贝祖定理来判断一个数组是否是「好数组」时,理论上并不需要所有元素都参与gcd的计算。如果数组中某个子集的元素的最大公约数为1,那么整个数组的最大公约数也必然为1。这是因为,如果子集的最大公约数为1,根据贝祖定理,可以找到这些元素的整数倍组合,其和为1。添加更多的其他元素并不会使得这个gcd变得更大。因此,虽然理论上不需要所有元素参与,但在算法实现中通常会遍历所有元素以保证全面性和简化程序逻辑。
🦆
代码中提早返回True的条件是当前gcd为1。在某些情况下,是否有可能最初几个元素的gcd为1,但加入后续元素后gcd改变?
一旦在计算过程中得到gcd为1,就不可能通过添加更多的元素使gcd改变为非1的值。这是由最大公约数的性质决定的:如果一组数的最大公约数为1,那么任何添加的数的最大公约数仍会是1,因为1是所有整数的公约数。因此,当我们在计算过程中得到gcd为1时,可以确信无论如何添加更多的数,这个gcd不会改变,所以提早返回True是合理的。
🦆
为什么初始化最大公约数g为0开始计算,而不是从数组的第一个元素开始?
在计算最大公约数时,初始化g为0是因为0与任何数n的最大公约数是n本身。这样的初始化方式允许我们从一个中立的基点开始累计计算最大公约数,不受数组起始元素的约束。这种方法简化了代码实现,使得gcd函数可以统一处理数组中的所有元素而不需要特别处理第一个元素。
🦆
如果数组中包含1,是否可以直接返回True,因为任何数和1的最大公约数为1?
是的,如果数组中包含1,则可以直接返回True。由于任何数与1的最大公约数必定为1,包含1的数组的最大公约数自然也是1。这意味着可以通过组合中至少包含一个1的方式,根据贝祖定理得出总和为1的组合,从而证明该数组是「好数组」。因此,在算法实现中,检测到1即可立即返回True,这是一个优化步骤。

相关问题