LeetCode 1250. 检查「好数组」

Categories:

题目描述
思路分析
1. 解法一：最大公约数判定（推荐）
相似题目

题目描述

✅ 1250. 检查「好数组」

思路分析

解法一：最大公约数判定（推荐）

核心思路：

数组可表示为所有元素线性组合，能组成 1 当且仅当所有元素的 gcd 为 1。

依次计算全数组 gcd，若最终 gcd 为 1 返回 true，否则 false。

复杂度分析：

时间复杂度：O(n log C)，其中 C 为元素最大值。

空间复杂度：O(1)。

class Solution {
    public boolean isGoodArray(int[] nums) {
        int g = 0;
        for (int v : nums) {
            g = gcd(g, v);
            if (g == 1) {
                return true;
            }
        }
        return g == 1;
    }

    private int gcd(int a, int b) {
        while (b != 0) {
            int t = a % b;
            a = b;
            b = t;
        }
        return Math.abs(a);
    }
}

func isGoodArray(nums []int) bool {
    g := 0
    for _, v := range nums {
        g = gcd(g, v)
        if g == 1 {
            return true
        }
    }
    return g == 1
}

func gcd(a, b int) int {
    if a < 0 {
        a = -a
    }
    if b < 0 {
        b = -b
    }
    for b != 0 {
        a, b = b, a%b
    }
    return a
}

相似题目

题目	难度	考察点
365. 水壶问题	中等	裴蜀定理
204. 计数质数	简单	数论
1404. 将二进制表示减到 1 的步骤数	中等	数学
858. 镜面反射	中等	数论
914. 卡牌分组	简单	最大公约数

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/20991398