關(guān)于最大公約數(shù)有專門的研究。 而在 LeetCode 中雖然沒有直接讓你求解最大公約數(shù)的題目。但是卻有一些間接需要你求解最大公約數(shù)的題目。
如何求最大公約數(shù)？
定義法
def GCD(a: int, b: int) -> int:
smaller = min(a, b)
while smaller:
if a % smaller == 0 and b % smaller == 0:
return smaller
smaller -= 1
復(fù)雜度分析
- 時(shí)間復(fù)雜度：最好的情況是執(zhí)行一次循環(huán)體，最壞的情況是循環(huán)到 smaller 為 1，因此總的時(shí)間復(fù)雜度為 O ( N ) O(N) O(N)，其中 N 為 a 和 b 中較小的數(shù)。
- 空間復(fù)雜度： O ( 1 ) O(1) O(1)。
輾轉(zhuǎn)相除法
如果我們需要計(jì)算 a 和 b 的最大公約數(shù)，運(yùn)用輾轉(zhuǎn)相除法的話。
首先，我們先計(jì)算出 a 除以 b 的余數(shù) c，把問題轉(zhuǎn)化成求出 b 和 c 的最大公約數(shù)；
然后計(jì)算出 b 除以 c 的余數(shù) d，把問題轉(zhuǎn)化成求出 c 和 d 的最大公約數(shù)；
再然后計(jì)算出 c 除以 d 的余數(shù) e，把問題轉(zhuǎn)化成求出 d 和 e 的最大公約數(shù)。
…
以此類推，逐漸把兩個(gè)較大整數(shù)之間的運(yùn)算轉(zhuǎn)化為兩個(gè)較小整數(shù)之間的運(yùn)算，直到兩個(gè)數(shù)可以整除為止。
def GCD(a: int, b: int) -> int:
return a if b == 0 else GCD(b, a % b)
更相減損術(shù)
輾轉(zhuǎn)相除法如果 a 和 b 都很大的時(shí)候，a % b 性能會(huì)較低。在中國，《九章算術(shù)》中提到了一種類似輾轉(zhuǎn)相減法的 更相減損術(shù)。它的原理是：兩個(gè)正整數(shù) a 和 b（a>b），它們的最大公約數(shù)等于 a-b 的差值 c 和較小數(shù) b 的最大公約數(shù)。
def GCD(a: int, b: int) -> int:
if a == b:
return a
if a < b:
return GCD(b - a, a)
return GCD(a - b, b)
上面的代碼會(huì)報(bào)棧溢出。原因在于如果 a 和 b 相差比較大的話，遞歸次數(shù)會(huì)明顯增加，要比輾轉(zhuǎn)相除法遞歸深度增加很多，最壞時(shí)間復(fù)雜度為 O(max(a, b)))。這個(gè)時(shí)候我們可以將輾轉(zhuǎn)相除法和更相減損術(shù)做一個(gè)結(jié)合，從而在各種情況都可以獲得較好的性能。
形象化解釋
下面我們對(duì)上面的過程進(jìn)行一個(gè)表形象地講解，實(shí)際上這也是教材里面的講解方式，我只是照搬過來，增加一下自己的理解罷了。我們來通過一個(gè)例子來講解：
假如我們有一塊 1680 米 * 640 米 的土地，我們希望將其分成若干正方形的土地，且我們想讓正方形土地的邊長盡可能大，我們應(yīng)該如何設(shè)計(jì)算法呢？
實(shí)際上這正是一個(gè)最大公約數(shù)的應(yīng)用場景，我們的目標(biāo)就是求解 1680 和 640 的最大公約數(shù)。
將 1680 米 * 640 米 的土地分割，相當(dāng)于對(duì)將 400 米 * 640 米 的土地進(jìn)行分割。 為什么呢？ 假如 400 米 * 640 米分割的正方形邊長為 x，那么有 640 % x == 0，那么肯定也滿足剩下的兩塊 640 米 * 640 米的。
實(shí)例解析
題目描述
給你三個(gè)數(shù)字 a，b，c，你需要找到第 n 個(gè)（n 從 0 開始）有序序列的值，
這個(gè)有序序列是由 a，b，c 的整數(shù)倍構(gòu)成的。
比如：
n = 8
a = 2
b = 5
c = 7
由于 2，5，7 構(gòu)成的整數(shù)倍構(gòu)成的有序序列為 [1, 2, 4, 5, 6, 7, 8, 10, 12, ...]，因此我們需要返回 12。
注意：我們約定，有序序列的第一個(gè)永遠(yuǎn)是 1。
大家可以通過 這個(gè)網(wǎng)站 在線驗(yàn)證。
一個(gè)簡單的思路是使用堆來做，唯一需要注意的是去重，我們可以使用一個(gè)哈希表來記錄出現(xiàn)過的數(shù)字，以達(dá)到去重的目的。
代碼：
ss Solution:
def solve(self, n, a, b, c):
seen = set()
h = [(a, a, 1), (b, b, 1), (c, c, 1)]
heapq.heapify(h)
while True:
cur, base, times = heapq.heappop(h)
if cur not in seen:
n -= 1
seen.add(cur)
if n == 0:
return cur
heapq.heappush(h, (base * (times + 1), base, times + 1))
對(duì)于此解法不理解的可先看下我之前寫的 幾乎刷完了力扣所有的堆題，我發(fā)現(xiàn)了這些東西。。。（第二彈）
然而這種做法時(shí)間復(fù)雜度太高，有沒有更好的做法呢？
實(shí)際上，我們可對(duì)搜索空間進(jìn)行二分。首先思考一個(gè)問題，如果給定一個(gè)數(shù)字 x，那么有序序列中小于等于 x 的值有幾個(gè)。
答案是 x // a + x // b + x // c 嗎？
// 是地板除
可惜不是的。比如 a = 2, b = 4, n = 4，答案顯然不是 4 // 2 + 4 // 4 = 3，而是 2。這里出錯(cuò)的原因在于 4 被計(jì)算了兩次，一次是 2 ? 2 = 4 2 * 2 = 4 2?2=4，另一次是 4 ? 1 = 4 4 * 1 = 4 4?1=4。
為了解決這個(gè)問題，我們可以通過集合論的知識(shí)。
一點(diǎn)點(diǎn)集合知識(shí)：
- 如果把有序序列中小于等于 x 的可以被 x 整除，且是 a 的倍數(shù)的值構(gòu)成的集合為 SA，集合大小為 A
- 如果把有序序列中小于等于 x 的可以被 x 整除，且是 b 的倍數(shù)的值構(gòu)成的集合為 SB，集合大小為 B
- 如果把有序序列中小于等于 x 的可以被 x 整除，且是 c 的倍數(shù)的值構(gòu)成的集合為 SC，集合大小為 C
那么最終的答案就是 SA ，SB，SC 構(gòu)成的大的集合（需要去重）的中的數(shù)字的個(gè)數(shù)，也就是：
問題轉(zhuǎn)化為 A 和 B 集合交集的個(gè)數(shù)如何求？
實(shí)際上， SA 和 SB 的交集個(gè)數(shù)就是 x // lcm(A, B)，其中 lcm 為 A 和 B 的最小公倍數(shù)。而最小公倍數(shù)則可以通過最大公約數(shù)計(jì)算出來：
def lcm(x, y):
return x * y // gcd(x, y)
接下來就是二分套路了，二分部分看不懂的建議看下我的二分專題。
代碼（Python3）：文章來源：http://www.zghlxwxcb.cn/news/detail-435171.html
class Solution:
def solve(self, n, a, b, c):
def gcd(x, y):
if y == 0:
return x
return gcd(y, x % y)
def lcm(x, y):
return x * y // gcd(x, y)
def possible(mid):
return (mid // a + mid // b + mid // c - mid // lcm(a, b) - mid // lcm(b, c) - mid // lcm(a, c) + mid // lcm(a, lcm(b, c))) >= n
l, r = 1, n * max(a, b, c)
while l <= r:
mid = (l + r) // 2
if possible(mid):
r = mid - 1
else:
l = mid + 1
return l
文章來源地址http://www.zghlxwxcb.cn/news/detail-435171.html
到了這里，關(guān)于每天一道算法練習(xí)題--Day22&& 第一章 --算法專題 --- ----------最大公約數(shù)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
