[已解决]我的方法有什么问题吗？谁能教教我？

Gigi233

在一个网站上做题，他说我的做法太复杂?谁能教教我

1. n1=max(a,b)
   
2. n2=min(a,b)
   
3. i = n1 // n2
   
4. while True:
   
5.     n=n2*i
   
6.     if n%n1==0:
   
7.         break
   
8. print(n)

复制代码

最佳答案

月排行榜 / 总排行榜

tommyyu

2023-3-12 17:19:58

去搜搜辗转相除法

1. a, b = 5, 3
   
2. n = a*b # 最小公倍数 = 两数之积 / 最大公约数
   
3. a, b = max(a, b), min(a, b)
   
4. while True:
   
5.     if b == 0:
   
6.         print(n // a) # 最小公倍数 = 两数之积 / 最大公约数
   
7.         break
   
8.     a, b = b, a % b

复制代码

你的复杂度是 O(ab) 的，辗转相除法的复杂度不到 O(a)

跳转到最佳答案楼层

Gigi233

求最小公倍数

tommyyu

去搜搜辗转相除法

1. a, b = 5, 3
   
2. n = a*b # 最小公倍数 = 两数之积 / 最大公约数
   
3. a, b = max(a, b), min(a, b)
   
4. while True:
   
5.     if b == 0:
   
6.         print(n // a) # 最小公倍数 = 两数之积 / 最大公约数
   
7.         break
   
8.     a, b = b, a % b

复制代码

你的复杂度是 O(ab) 的，辗转相除法的复杂度不到 O(a)

君无泪

什么网站可以做题？想练练手，找不到题。

qq1151985918

君无泪 发表于 2023-3-13 00:02
什么网站可以做题？想练练手，找不到题。

力扣了解一下

君无泪

qq1151985918 发表于 2023-3-13 00:24
力扣了解一下

多谢

zhangjinxuan

如果 A,B 都是 一百万 以内的，那么这个就是对的，但是，你忘了i++

如果都是那种 一百万以上的，可以参照楼上的辗转相除法

Gigi233

君无泪 发表于 2023-3-13 00:02
什么网站可以做题？想练练手，找不到题。

我用的这个叫pythontip

Gigi233

tommyyu 发表于 2023-3-12 17:19
去搜搜辗转相除法
你的复杂度是 O(ab) 的，辗转相除法的复杂度不到 O(a)

好的 我研究一下 非常感谢！

Gigi233

zhangjinxuan 发表于 2023-3-13 07:33
如果 A,B 都是 一百万 以内的，那么这个就是对的，但是，你忘了i++

如果都是那种 一百万以上的，可以参 ...

好的，我学习一下！

Gigi233

tommyyu 发表于 2023-3-12 17:19
去搜搜辗转相除法
你的复杂度是 O(ab) 的，辗转相除法的复杂度不到 O(a)

想问下b==0是啥意思呀