检查「好数组」
难度:
标签:
题目描述
代码结果
运行时间: 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?
▷🦆
代码中提早返回True的条件是当前gcd为1。在某些情况下,是否有可能最初几个元素的gcd为1,但加入后续元素后gcd改变?
▷🦆
为什么初始化最大公约数g为0开始计算,而不是从数组的第一个元素开始?
▷🦆
如果数组中包含1,是否可以直接返回True,因为任何数和1的最大公约数为1?
▷