Greatest Common Divisor
题目地址:
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
推荐阅读
-
typecho Call to undefined method Typecho_Common::lockHTML()
-
Error:Could not find common.jar (android.arch.core:common:1.0.0)
-
是怎么用的?_html/css_WEB-ITnose
-
14. Longest Common Prefix 最长公共前缀
-
Leetcode-14 Longest Common Prefix
-
NO14. Longest Common Prefix (Easy) (Java)
-
Uchome1.2 1.5 代码学习 common.php_PHP教程
-
oracle中的greatest 函数和 least函数示例代码
-
关于SQL中CTE(公用表表达式)(Common Table Expression)的总结
-
ThinkPHP调用common/common.php函数提示错误function undefined的解决方法