跳到主要内容

1250.检查「好数组」

· 阅读需 3 分钟

1、题干​

给你一个正整数数组 nums，你需要从中任选一些子集，然后将子集中每一个数乘以一个 任意整数，并求出他们的和。

假如该和结果为 1，那么原数组就是一个「好数组」，则返回 True；否则请返回 False。

 

示例 1：

输入：nums = [12,5,7,23]
输出：true
解释：挑选数字 5 和 7。
5*3 + 7*(-2) = 1

示例 2：

输入：nums = [29,6,10]
输出：true
解释：挑选数字 29, 6 和 10。
29*1 + 6*(-3) + 10*(-1) = 1

示例 3：

输入：nums = [3,6]
输出：false

 

提示：

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

2、思路​

这不是我能写出来的题，看了提示才AC

根据提示，要求所有数字的最大公约数是否等于1。想到的思路是：先升序排序 nums 数组，如果存在相邻数字的最大公约数 gi 等于1，或者 gi 与 gcd(nums[0],nums[1]) 的最大公约数等于1，那么 nums 是一个好数组。虽然过了，但无法证明算法正确性

3、代码​

function isGoodArray(nums: number[]): boolean {
    nums.sort((a, b) => a - b);
    const gcd = (a: number, b: number) => a ? gcd(b % a, a) : b;

    const g1 = gcd(nums[0], nums[1] || 0);

    for (let i = 1; i < nums.length; i++) {
        const gi = gcd(nums[i], nums[i + 1]);
        if (gi === 1 || gcd(g1, gi) === 1) return true;
    }

    return g1 === 1;
};

官解根据裴蜀定理推论和证明，严谨很多，代码也不难。整体思路也是求所有数字的最大公约数是否等于1

function isGoodArray(nums: number[]): boolean {
    let d = nums[0];
    const gcd = (a: number, b: number) => a ? gcd(b % a, a) : b;

    for (let i = 0; i < nums.length && d !== 1; i++) {
        d = gcd(d, nums[i]);
    }

    return d === 1;
};

4、复杂度​

  • 时间复杂度：O(nlogn)O(nlogn)
  • 空间复杂度：O(logn)O(logn)

5、执行结果​

image.png