Easy

题目描述

给你一个下标从 0 开始的整数数组 nums 。如果下标对 i, j 满足 0 ≤ i < j < nums.length ，且 nums[i] 的 首位数字 和 nums[j] 的 末位数字 互质，则认为 (i, j) 是一个 美丽对 。

返回 nums 中 美丽对 的总数目。

对于两个整数 x 和 y ，如果不存在大于 1 的整数可以整除它们，则认为 x 和 y 互质 。换句话说，如果 gcd(x, y) == 1 ，其中 gcd(x, y) 是 x 和 y 的最大公约数，则 x 和 y 互质。

示例 1：

输入：nums = [2,5,1,4]
输出：5
解释：nums 中共有 5 个美丽对：
i = 0 和 j = 1 ：nums[0] 的首位数字是 2 ，nums[1] 的末位数字是 5 。gcd(2,5) == 1 ，所以 2 和 5 互质。
i = 0 和 j = 2 ：nums[0] 的首位数字是 2 ，nums[2] 的末位数字是 1 。gcd(2,1) == 1 ，所以 2 和 1 互质。
i = 1 和 j = 2 ：nums[1] 的首位数字是 5 ，nums[2] 的末位数字是 1 。gcd(5,1) == 1 ，所以 5 和 1 互质。
i = 1 和 j = 3 ：nums[1] 的首位数字是 5 ，nums[3] 的末位数字是 4 。gcd(5,4) == 1 ，所以 5 和 4 互质。
i = 2 和 j = 3 ：nums[2] 的首位数字是 1 ，nums[3] 的末位数字是 4 。gcd(1,4) == 1 ，所以 1 和 4 互质。
因此，返回 5 。

示例 2：

输入：nums = [11,21,12]
输出：2
解释：共有 2 个美丽对：
i = 0 和 j = 1 ：nums[0] 的首位数字是 1 ，nums[1] 的末位数字是 1 。gcd(1,1) == 1 ，所以 1 和 1 互质。
i = 0 和 j = 2 ：nums[0] 的首位数字是 1 ，nums[2] 的末位数字是 2 。gcd(1,2) == 1 ，所以 1 和 2 互质。
因此，返回 2 。

提示：

  • 2 <= nums.length <= 100
  • 1 <= nums[i] <= 9999
  • nums[i] % 10 != 0

解题思路

这道题的核心是理解美丽对的定义：对于下标对 (i, j)，需要 nums[i] 的首位数字与 nums[j] 的末位数字互质。

解题思路：

  1. 提取数字：对于每个数字，我们需要提取首位数字和末位数字。末位数字可以通过 num % 10 获得，首位数字可以通过不断除以 10 直到只剩一位数获得。

  2. 暴力枚举：由于数组长度最大只有 100，我们可以使用双重循环枚举所有可能的下标对 (i, j)，其中 i < j。

  3. 互质判断：对于每一对 (i, j)，提取 nums[i] 的首位数字和 nums[j] 的末位数字，然后计算它们的最大公约数。如果最大公约数为 1，则这一对是美丽对。

算法步骤：

  • 遍历所有满足 i < j 的下标对
  • 对每一对，提取相应的首位和末位数字
  • 使用欧几里得算法计算最大公约数
  • 统计互质的对数

这种方法时间复杂度为 O(n²)，对于题目给定的数据范围完全可以接受。

代码实现

class Solution {
public:
    int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
    
    int getFirstDigit(int num) {
        while (num >= 10) {
            num /= 10;
        }
        return num;
    }
    
    int getLastDigit(int num) {
        return num % 10;
    }
    
    int countBeautifulPairs(vector<int>& nums) {
        int count = 0;
        int n = nums.size();
        
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int firstDigit = getFirstDigit(nums[i]);
                int lastDigit = getLastDigit(nums[j]);
                
                if (gcd(firstDigit, lastDigit) == 1) {
                    count++;
                }
            }
        }
        
        return count;
    }
};

class Solution:
    def countBeautifulPairs(self, nums: List[int]) -> int:
        def gcd(a, b):
            while b:
                a, b = b, a % b
            return a
        
        def get_first_digit(num):
            while num >= 10:
                num //= 10
            return num
        
        def get_last_digit(num):
            return num % 10
        
        count = 0
        n = len(nums)
        
        for i in range(n):
            for j in range(i + 1, n):
                first_digit = get_first_digit(nums[i])
                last_digit = get_last_digit(nums[j])
                
                if gcd(first_digit, last_digit) == 1:
                    count += 1
        
        return count

public class Solution {
    private int Gcd(int a, int b) {
        return b == 0 ? a : Gcd(b, a % b);
    }
    
    private int GetFirstDigit(int num) {
        while (num >= 10) {
            num /= 10;
        }
        return num;
    }
    
    private int GetLastDigit(int num) {
        return num % 10;
    }
    
    public int CountBeautifulPairs(int[] nums) {
        int count = 0;
        int n = nums.Length;
        
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int firstDigit = GetFirstDigit(nums[i]);
                int lastDigit = GetLastDigit(nums[j]);
                
                if (Gcd(firstDigit, lastDigit) == 1) {
                    count++;
                }
            }
        }
        
        return count;
    }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var countBeautifulPairs = function(nums) {
    function gcd(a, b) {
        while (b !== 0) {
            let temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
    
    function getFirstDigit(num) {
        while (num >= 10) {
            num = Math.floor(num / 10);
        }
        return num;
    }
    
    function getLastDigit(num) {
        return num % 10;
    }
    
    let count = 0;
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            let firstDigit = getFirstDigit(nums[i]);
            let lastDigit = getLastDigit(nums[j]);
            if (gcd(firstDigit, lastDigit) === 1) {
                count++;
            }
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(n²)
空间复杂度O(1)

说明：

  • 时间复杂度：双重循环遍历所有可能的下标对，每次调用 gcd 函数的时间复杂度为 O(log min(a,b))，但由于数字范围很小（首位和末位数字都是 1-9），可以视为常数时间
  • 空间复杂度：只使用了常数个额外变量