题目地址：
https://www.lintcode.com/problem/greatest-common-divisor/description
求两个正整数的最大公约数。
思路是辗转相除法。代码如下：
public class Solution {
/**
* @param a: the given number
* @param b: another number
* @return: the greatest common divisor of two numbers
*/
public int gcd(int a, int b) {
// write your code here
if (a * b == 0) {
return a + b;
}
while (b != 0) {
int tmp = a % b;
a = b;
b = tmp;
}
return a;
}
public static void main(String[] args) {
System.out.println(new Solution().gcd(10, 15));
}
}
时间复杂度
O
(
log
max
{
a
,
b
}
)
O(\log \max\{a,b\})
O(logmax{a,b})（原因是
(
a
,
b
)
(a,b)
(a,b)的减少速度一定至少快于斐波那契数列，而斐波那契数列的增长速度是指数级的），空间
O
(
1
)
O(1)
O(1)。
本文地址：https://blog.csdn.net/qq_46105170/article/details/110228209
