欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Greatest Common Divisor

程序员文章站 2022-04-15 18:23:01
题目地址: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 num...

题目地址:

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