孝感网站建设公司,潍坊地区制作网站,云南住房与城乡建设厅网站,直播营销策划方案题目链接#xff1a;https://leetcode.cn/problems/check-if-it-is-a-good-array/description/
思路
方法#xff1a;数论
题目意思很简单#xff0c;让你在数组 nums中选取一些子集#xff0c;可以不连续#xff0c;子集中的每个数再乘以任意的数的和是否为1#xff…
题目链接https://leetcode.cn/problems/check-if-it-is-a-good-array/description/
思路
方法数论
题目意思很简单让你在数组 nums中选取一些子集可以不连续子集中的每个数再乘以任意的数的和是否为1是则原数组就是个「好数组」
关键词每个数相乘任意一个数相加数论里「裴蜀定理」是一个关于最大公约数的定理。也是拥有类似的推导具体证明可参考「裴蜀定理」OI Wiki。 「裴(pei)蜀定理」设 a,b 是不全为零的整数则存在整数 x,y, 使得 axby gcd(a,b). 「裴蜀定理」同样也可以推广到多个整数的情况。对于全不为 0 的任意 n 个整数 a1, a2, a3, a4 … an记这 n 个整数的最大公约数为 0则对于任意 n 个整数 x1, x2, x3, x4 … xn都满足 ∑i1nai∗xi\sum_{i1}^{n} a_i * x_i∑i1nai∗xi 是 g 的倍数。
推论正整数 a1 到 an 的最大公约数是 1 的充分必要条件是存在 n 个整数 x1 到 xn 满足 ∑i1nai∗xi1\sum_{i1}^{n} a_i * x_i 1∑i1nai∗xi1
回到原题我们判断数组 nums 是否是个「好数组」。由「裴蜀定理」推导 0 i n题目等价于求 nums 中的全部数字的最大公约数是否等于 1若等于 1 则原数组为「好数组」否则不是。
如何求数组 nums 的 最大公约数 g初始化 g nums[0]遍历数组更新 g gcd(g, nums[i])遍历完全部数字后g 即为数组 nums 中全部的元素的最大公约数。然后判断其是否等于 1 即可。在实现过程中我们也可以进一步做优化如果遍历过程中出现最大公约数等于 1 的情况则由于 1 和任何正整数的最大公约数都是 1此时可以提前结束遍历。
代码示例
func isGoodArray(nums []int) bool {// 有数据为[1]的情况if len(nums) 1 nums[0] 1{return true}g : nums[0]for i : 1; i len(nums); i {g gcd(g, nums[i])if g 1 {return true}}return false
}func gcd(a, b int) int {if a % b 0 {return b}return gcd(b, a % b)
}复杂度分析
时间复杂度O(n logm\log mlogm)其中n表示数组 nums 长度m 表示与最大公约数 g 迭代次数最长的数字其中求单次最大公约数的时间复杂度为 O(logm\log mlogm)两个数求最大公约数其中最大公约数 g 自增不减总的求最大公约数所需时间为O(logm\log mlogm)所以总的所需时间O(n logm\log mlogm)空间复杂度O(1)不需要额外申请空间
