常见算法

发表于 更新于 分类于

概要

  • 辗转相除法求最大公约数

最大公约数

最大公约数-题目

给你一个整数数组 nums ，返回数组中最大数和最小数的 最大公约数 。

两个数的 最大公约数 是能够被两个数整除的最大正整数。

辗转相除法

辗转相除法，又称 欧几里得算法，对于两个非负整数 $x,y (x>y)$，其计算公式为：
$$gcd(x,y)=gcd(y, x \text{ mod } y)$$

1
2
3
4
5
6
7
8
9
10
class Solution:
    def findGCD(self, nums: List[int]) -> int:   
   
        def gcd(maxn, minn):
            if minn == 0:
                return maxn
            return gcd(minn, maxn % minn)
        
        mx, mn = max(nums), min(nums)
        return gcd(mx, mn)
1
2
3
4
5
6
7
8
9
10
class Solution:
    def findGCD(self, nums: List[int]) -> int:

        def gcd(maxn, minn):     
            while y:
                maxn, minn = minn, maxn % minn
            return maxn

        mx, mn = max(nums), min(nums)
        return gcd(mx, mn)

遍历实现求最大公约数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int findGCD(int* nums, int numsSize){
    int i;
    int min = INT_MAX, max = INT_MIN;

    // 找到最大值和最小值
    for (i = 0; i < numsSize; i++) {
        if (nums[i] > max)
            max = nums[i];
        if (nums[i] < min)
            min = nums[i];
    }
    
    // 最大公约数的 最大可能值 = 最小值
    // 所以 i 从 min 开始
    for (i = min; i > 0; i--) {
        if (max % i == 0 && min % i == 0) 
            return i;
    }

    return 1;
}

调gcd包

1
2
3
4
5
6
7
8
class Solution {
public:
    int findGCD(vector<int>& nums) {
        int mx = *max_element(nums.begin(), nums.end());
        int mn = *min_element(nums.begin(), nums.end());
        return gcd(mx, mn);
    }
};
1
2
3
4
5
6
import math

class Solution:
    def findGCD(self, nums: List[int]) -> int:
        mx, mn = max(nums), min(nums)
        return math.gcd(mx, mn)